+1 Daumen
1,3k Aufrufe

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

2 Antworten

0 Daumen

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ß

Avatar von 23 k

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.

0 Daumen

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;

Bild Mathematik

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

Bild Mathematik

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community