1000-er Reste von hohen Potenzen

Question

In einer Aufgabe soll man die 1000er Reste von
a) 7^9999
b)11^9999
c) 13^9999

bestimmen. Dies soll unter Berücksichtigung der eulerschen Phi-Funktion geschehen.

Kann mir dabei jemand helfen?

vG

Answer 1

Alles beschrieben bei Wikipedia Eulersche_Phi-Funktion

Der Rechner unter http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

benutzt diese bei pow(x,y) modulo N

Mit N=1000 bekommt man so die letzten 3 Stellen dieser gigantischen Zahl (größer als die Anzahl der Atome im Weltall!!)

Comments

Erstmal danke.

Also bei Wikipedia blicke ich im Hinblick auf die Aufgabe nicht durch, und der Rechner spuckt zwar Zahlen aus,aber dadurch wird der Weg nicht klar. Hättest du eventuell einen nachvollziehbaren Lösungsansatz? (vor allem für die Teile b und c)