Förenkla 2^30 (mod 3)
Hej, hörni
Jag undrar hur man skall lösa
Förenkla 2^30 (mod 3).
Det jag tänkte var att man kan förvandla 2^30 till 2^5 * 2^5 * 2^5 * 2^5 * 2^5 * 2^5 och sedan multiplicera alla dess rester. Detta ger då 3^6 = 729. 729 (mod 3). Från här vet jag ej hur man skall gå vidare.
I facit säger de 1 (mod 3). Jag förstår inte hur dem kom fram till det. Är det kanske så att de tänkte sig en klocka med tre timmars kapacitet, och att man går 2-timmarsvarv 30 gånger och då hamnar man på timme 1 av 3 på trettionde varvet?
Lättare är att hitta en exponent som ger rest 1 vid heltalsdivision med 3. Redan vid 2² så har vi hittat en sådan, men eftersom exponenten är jämn har vi ett jämnt antal 2² så att resten är 1 eftersom 2² är kongruent med 2^(30) mod 3.
Varför? Eftersom 2⁶ är 2²*2²*2²=1³ mod 3, oxh samma sak händer oavsett expinenten så länge den är jämn.
Dracaena skrev:Lättare är att hitta en exponent som ger rest 1 vid heltalsdivision med 3. Redan vid 2² så har vi hittat en sådan, men eftersom exponenten är jämn har vi ett jämnt antal 2² så att resten är 1 eftersom 2² är kongruent med 2^(30) mod 3.
Varför? Eftersom 2⁶ är 2²*2²*2²=1³ mod 3, oxh samma sak händer oavsett expinenten så länge den är jämn.
Tack så hemskt mycket för ett otroligt snabbt och bra svar! Nu kan jag fortsätta med kapitlet :)
Varför skriver du om det som 230 = (25)6? Visst, 25 = 32 som är kongruent med -1 modulo 3, så du har att 230 = (-1)6 = ...
Men det finns ett enkare (tycker jag i alla fall) sätt!
22=4 som är kongruent med 1 modulo 3. 230kan alltså skrivas som( 22)15 som är kongruent med 115 som är kongruent med... Kommer du vidare?
EDIT: Hade jag sett Dracaenas svar hade jag nog inte skrivit det här...
