Kan jag förenkla uträkningen?

Ska beräkna vilken rest det blir med från 2^185 division med 9.

$2^{185 = {(2^{5})}^{37}^{} = 32^{37} \equiv 5^{37} (\mod 9) = 5^{36} \cdot 5 = {(5^{2})}^{18} \cdot 5 = 25^{18} \cdot 5 \equiv 7^{18} \cdot 5 = {(7^{2})}^{9} \cdot 5 =}$

$= 49^{9} \cdot 5 \equiv 4^{9} \cdot 5 (\mod 9) = 4^{3} \cdot 4^{3} \cdot 4^{3} \cdot 5 = 64 \cdot 64 \cdot 64 \cdot 5 \equiv 1 \cdot 1 \cdot 1 \cdot 5 (\mod 9) \equiv 5 (\mod 9)$

Svar: $2^{185} \equiv 5 (\mod 9)$

Ja. Lägg märke till att 2⁶ = 64 = 63+1 så 2⁶ är kongruent med 1 modulo 9

2¹⁸⁵ = (2⁶)^30.2⁵ är kongruent med 1³⁰^.2⁵ =2⁵ = 32 = 27+5 så du har helt rätt i att 2¹⁸⁵ är kongruent med 5 modulo 9.

Det är en bra metod att försöka hitta något som är kongruent med 1 (eller med -1, det är bara liiite krångligare) och bryta ut dessa potenser så att man får något mer hanterligt kvar.

Ja det där blev ju lite kortare uträkning, tack för hjälp och tips. :)

Ju färre steg, desto mindre risk att man räknar fel...

Svara

Visa senaste svar