wie bestimmt man die letzten vier Ziffern von 1001^20002?

Question

Kam mir jemand sagen wie ich das berechnen soll? Bedanke mich im Voraus.

Answer 1

Edit: Ups hab eine Stelle zuviel gelesen.

zum Beispiel kannst du mit dem binomischen Lehrsatz argumentieren, dass die letzen 4 Ziffern  2001 sind.

Alternative aus der Zahlentheorie: Satz von Euler verwenden.

Gruß

Comments

Ich weiß was der Satz von Euler ist...ich komme trotzdem nicht weiter. 

---

Aus deiner letzten Aufgabe sollte dir inzwischen klar sein, dass \(\varphi(10000) = 4000\).

Jetzt betrachte:

$$ 1001^{20002} \mod 10000 = (1001^{4000})^5 \cdot 1001^2 \mod 10000 $$

---

Das macht mich gerade durcheinander. Wie soll ich den Satz jetzt anwenden? 

---

...

Nach dem Satz von Euler ist \( 1001^{4000} \mod 10000 = 1 \).

Somit steht oben in der Gleichung hinterher nur noch \(...=1001^2 \mod 10000\), was sich per Hand berechnen lässt.

Answer 2

Es gibt die super schnelle Funktion Modulo = Divisionsrest.

Um die letzten 4 Stellen von x zu bekommen:  x mod (10^4)

= x mod 10000 = x % 10000 (in JavaScript und php)

Bei großen Potenzen gibt es den Pow-Mod Algorithmus, der schon während des Potenzierens Abkürzungen nutzt, statt das Zwischenergebnis extrem groß werden zu lassen.

Wie man x = pow(1001,20002) mod 10000 löst, zeigt Beispiel 122 des Iterationsrechners:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm

Die 3 Parameter anpassen: aB[0]=a=1001;b=20002;c=10000;

Die Zwischenergebnisse werden in der Tabelle darunter mit angezeigt: nach 15 Schritten (Iterationen)

liegt das Ergebnis in der letzten Feldvariable aC[d]. 

Hinweise: pow(x,y) = x^y

floor(x) = Abrunden bis zur nächsten ganzen Zahl

Auch der wissenschaftliche Umkehrfunktionen Rechner kann extrem große Zahlen potenzieren mit Mod:

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php