Hohe Potenzen Rechnen?(Chinesischer Restsatz, kleiner Fermatscher Satz?
Hey,
wie berechne ich die Hohe Potenz wenn kleiner Fermatscher Satz nicht funktioniert. Ich müsste dann den Chinesischen Restesatz nutzen aber wie wende ich ihn an wenn ich
17^866 mod 247 habe. Ich wäre euch Dankbar wenn jemand mir erklären könnte wie man diese Aufgabe berechnet. Ich verstehe den Chinesischen Restsatz leider nicht...
3 Antworten
Den Tip 247 = 13 * 19 hast du ja schon von aperfect10 bekommen.
Mit dem Satz von Euler, der Verallgemeinerung des kleinen Fermat, hat man in diesem Fall
17^((13-1)*(19-1)) = 1 mod (13*19), also
17^216 = 1 mod (13*19).
Wegen 866 = 4 * 216 + 2 bleibt dann noch
17^866 = 17^2 = 42 mod (13*19).
Wieder mal 42, die Antwort auf eh alles ...
Wenn du den Satz von Euler nicht verwenden darfst, machst du es wie von ChrisGE1267 vorgeschlagen.
Sei x = 17^866 mod 247, also x - 17^866 = 0 mod (13*19).
Dann ist x - 17^866 = 0 mod 13 und x - 17^866 = 0 mod 19.
Nach dem kleinen Fermat gilt für eine Primzahl p: a^p = a mod p. Damit kannst Du die simultanen Kongruenzen
x = 17^866 = 4^866 mod 13 und x = 17^866 = (-2)^866 mod 19
einfach lösen…
Tipp: