räkning med kongruenser

Har stött på ett problem:

"vilken rest erhålls då 207^61 divideras med 13?"

Jag börjar med att dividera 207 med 13 och får resten 12.
Alltså är 207 kongruent med 12 mod 13.

Sedan söker jag efter en potens n till 207 som gör att talet 207^n är kongruent med 1 mod 13.

Potensen 2 är den jag söker efter, alltså: 207^2 är kongruent med 1 mod 13. Men potensen ska ju vara 61. Kan man inte bara "höja upp" båda sidor med 61/2 ?

Då får man ju att 207^61 är kongruent med 1^(61/2) mod 13 vilket är samma som 1 mod 13.

Borde inte resten vara 1 isåfall? Facit säger 12, vilket är det svar som jag får som rest när jag dividerar 207 med 13. Vad hände med potensen?

någon som kan förklara?

tack

207^61 mod 13

207 == 12 mod 13
12 == -1 mod 13

Så 207^61 mod 13 är samma sak som:
(-1)^61 mod 13 ...

(-1)^61 = -1 ... som är samma element som 12 i Z13. Så resten är 12

Jag har verkligen ingen koll på kongruenser. 207^61 mod 13 ? Vart får du det ifrån?
tex 207==12mod13 betyder ju att man får 12 i rest när man delar 207 med 13. Men 207^61 mod 13? Jag förstår inte...

Det finns en regel som säger att om a == b (mod n), där n>=2 är ett heltal, så gäller även att a^m == b^m (mod n) för naturliga tal m.

För att du skall förstå varför tar vi fallet m=3:
a == b (mod n) betyder att a - b är delbart med n, dvs a = b + k n för något heltal k. Då är
a^3 = (b + k n)^3 = b^3 + 3 b^2 k n + 3 b k^2 n^2 + k^3 n^3 = b^3 + (3 b^2 k + 3 b k^2 n + k^3 n^2) n,
så
a^3 - b^3 = (3 b^2 k + 3 b k^2 n + k^3 n^2) n,
som är delbart med n.
Alltså gäller att a^3 == b^3 (mod n).

Så, eftersom 207 == 12 == -1 (mod 13), gäller enligt ovanstående regel att 207^61 == (-1)^61 (mod 13). Men (-1)^61 = -1, så 207^61 == -1 == 12 (mod 13).

Förutom mannes svar kan man ju göra så här:

207 = 13*16 - 1, du vill få ut vad 207^61 modulus 13 blir ...

Eftersom 207 = 13*16 - 1 så är 207^61 samma sak som:

(13*16 - 1)^61 som man kan utveckla med hjälp av binomial... till

(61 0) (13*16)^61*(-1)^0 + (61 1) (13*16)^60*(-1)^1 + (62 2) * (13*16)^59 * (-1)^2 ... + (-1)^61

Alla termer är delbara med 13 utom termen (-1)^61 därför är resten samma sak som (-1)^61 ... och (-1)^61 = -1. Så resten är -1 som är samma element som 12.