+2 Daumen
1,9k Aufrufe

Berechne ohne Taschenrechner:

$$\left [ 3 \right ]^{2014^{2014}} \mod 98$$

Ich weiß, dass ich den Satz von Euler-Fermat anwenden muss. Als Tipp ist gegeben, dass wenn der Satz nicht gleich anwendbar ist, dass man den Chinesischen Restsatz machen sollte.

Ich weiß, wie der Satz von Euler-Fermat geht bei Zahlen wie $$5^{256} \mod 13$$

Aber bei so großen Zahlen verstehe ich es nicht, mich verwirrt vor allem die doppelte Hochzahl.

Ich habe schon einmal so angefangen (für den CR):

$$98 = 2*7^{2}\\ \left [3  \right ]^{2014^{2014}} \mod 2 \\ \left [3  \right ]^{2014^{2014}} \mod 49$$

Jetzt die beiden ausrechnen:

$$\left [3  \right ]^{2014^{2014}\mod \phi_{(2)} = 2} \equiv  \left [3  \right ]^{0} \equiv 1  \mod 2$$

Das war ein Glücksfall.
Bei mod 49 scheitere ich.

Wenn ich einfach stur den Satz von Euler-Fermat auf 2014^2014 anwende passiert folgendes:
$$\phi _{(49)} = 42\\ 2014 = 47*42+40\\ 2014^{2014} = 2014^{42^{47}}*2014^{40}\equiv 2014^{40} \mod 49$$

(Ohne Taschenrechner geht das auch nicht wirklich.)
Und was jetzt, auf 2014^40 mod 49 kann ich den Satz von EF nicht noch einmal anwenden. Und im Kopf kann ich es auch nicht.

Avatar von

2014^40 mod 49 = 2 -> Aber was willst Du damit bezwecken???

1 Antwort

+1 Daumen
 
Beste Antwort

ohne Klammern geht hoch vor Punktrechnung!

mit dem pow-mod-Algorithmus http://www.gerdlamprecht.de/Roemisch_JAVA.htm#ZZZZZ0122

kann man a^b mod c auch für große Zahlen berechnen.

3^{2014^1} mod 98 =11

3^{2014^2} mod 98 =81

3^{2014^3} mod 98 =39

3^{2014^4} mod 98 =25

3^{2014^5} mod 98 =53

3^{2014^6} mod 98 =95

3^{2014^7} mod 98 =11 ab hier Periode!!!! also die Viel fachen von 6 mit der Formel x*6+4

und da 335 * 6 + 4 = 2014

3^{2014^2014} mod 98 = 3^{2014^4} mod 98 = 25 Endergebnis 

2014^4 = 16452725990416 

Kontrolle : 3^16452725990416 mod 98  per http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

Bild Mathematik

Bild Mathematik

Beide stimmen: 25

Avatar von 5,7 k

Vermutlich wolltest Du folgenden Weg gehen:

EulerPhi(98)=42

2014 = 47*42+40

3^2014^40 mod 98 =25 stimmt, denn die 40 ist auch Vielfache von 6+4: 6*6+4


Und noch zu 3^16452725990416 mod 98 per Iterationsrechner:

(und ja, es geht auch mit mod 49 -> selbe b=25)

hier noch der untere Bildausschnitt:

nach i=22 Schritten hat man das Ergebnis -> also auch ohne Taschenrechner berechenbar

Bild Mathematik

Und wer will, kann bis  3^16 mod 98 =3^16 mod 49 = 25 runtergehen...

Interessant: diese hypergroße Zahl hat mehr als 10^6654 Dezimalstellen!!!

Da unser Weltall nicht mal aus 10^80 Atomen bestehlt, wird es nie möglich sein, auch nur Bruchteile davon abzubilden!

Aber mit den Modulo-Gesetzen kann man bestimmen, dass diese Zahl geteilt durch 98 den Rest 25 ergibt.

...und mit den Ziffern ...409246721 endet. :-)


Falls doch eine Klammer vorhanden war (3^2014)^2014

= (8.360014012980639246803759144... e960)^2014=(8.36001401298...*10^960)^2014

sind es "nur 1935298 " Dezimalstellen

Danke für diese Lösung!

Wegen der Klammer, in der Angabe steht es so:

Bild Mathematik

Neu: die PowPowMod(x,y,z,h) Funktion unter

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

kann jetzt diese und noch extrem größere Potenzen direkt per

CarmichaelLambda Algorithmus berechnen.

366355555555555551234567366355555555555551234563^247731234567111111111113366355555555555551234565^428630000000000000000555366355555555555551234567 mod 25641167830000000000000000000000 = 24309440616441764942524290735443

( das kann nicht mal Wolfram Alpha)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community