beräkna resten med Moduloräkning

Hej! Jag har en inlämningsuppgift och har inte räknat med modulo innan så vill se så jag tänkt rätt.

$B e r ä k n a r e s t e n d å 2^{177} d e l a s m e d 5$

Jag har använt mig av

$2^{3} = 8 8 \equiv_{5} 3$

$2^{177} = 2^{3 * 59} = {(2^{3})}^{59} {(2^{3})}^{59} \equiv_{5} 2^{59}$

$2^{59} = 2^{3 * 19 + 2} = {(2^{3})}^{19} * 2^{2}$

^{$(2$ ³)19*22≡5219*22=221}

$2^{21} = 2^{3 * 7} = (2$ ³)7

$(2$ ³)7≡527

$2^{7} = 2^{3 * 2 + 1} = (2$ ³)2*2

$(2$ ³)2*2≡522*2

$2^{2} * 2 = 8 8 - 5 = 3$

Svar: resten är 3

En bra ansats är att fundera över vilken två-potens som är lika med 1(mod5) alternativt -1(mod 5).

Det såg lite konstigt ut med ekvationerna trots att jag redigerat så skickar även det jag skrivit, är det fel tänkt?

Varför använder du dig inte av tipset från dr_lund och utnyttjar att 2⁴ är kongruent med 1 (modulo 5)?

Tack för hjälpen!
Menar ni då att eftersom

$2^{4} \equiv 1 (m o d 5) \frac{2^{4}}{5} = 3, 2 \frac{1}{5} = 0, 2 g e r e n r e s t p å 3$

Är det första sättet jag skrev på fel eller mest bara onödigt?

[2¹⁷⁷]₅ = [2]₅^{44 x 4 +1} = [2⁴]₅⁴⁴ [2]₅= [1]₅⁴⁴[2]₅ = [1]₅[2]₅ = [2]₅

axewh skrev:
Tack för hjälpen!
Menar ni då att eftersom
$2^{4} \equiv 1 (m o d 5) \frac{2^{4}}{5} = 3, 2 \frac{1}{5} = 0, 2 g e r e n r e s t p å 3$

Är det första sättet jag skrev på fel eller mest bara onödigt?

Man kan inte dividera på det viset med moduloräkning. Använd samma metod som du gjorde men använd 2⁴ i stället för 2³. Det du gjorde är inte fel, men blev onödigt långt med 2³.

Jahaaa . nu fattar jag! blev lite förvirrad där ett tag, första gången jag räkna med modulo hehe! Så jag ska tänk som jag skrivit i min bifogade bild då?

Redan med (2⁴)⁴⁴*2 är du nästan klar, för 2⁴ är ju 1 modulo 5, så det blir 1⁴⁴*2 som blir 1*2 = 2.

Du verkar få 2⁴ till 2 i stället för 1 ibland.

Det är nog fel i din tidigare uträkning också, eftersom den också får svaret 3. Jag tittade inte så noga på den.

Svara

Visa senaste svar