Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Satz von Euler-Fermat: [3]^2014^2014 mod 98

Satz von Euler-Fermat: [3]^2014^2014 mod 98

Universität / Fachhochschule

Teilbarkeit

Tags: euler, eulersche Phi-Funktion, Fermat, Teilbarkeit

DiMaGuy aktiv_icon

21:37 Uhr, 30.04.2015

Berechne ohne Taschenrechner:

{[3]}^{201 4^{2014}} \ m o d 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} \ m o d 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}

{[3]}^{201 4^{2014}} \ m o d 2

{[3]}^{201 4^{2014}} \ m o d 49

Jetzt die beiden ausrechnen:

{[3]}^{201 4^{2014} \ m o d φ_{(2)} = 2} \equiv {[3]}^{0} \equiv 1 \ m o d 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:

φ_{(49)} = 42

2014 = 47 * 42 + 40

201 4^{2014} = 201 4^{4 2^{47}} * 201 4^{40} \equiv 201 4^{40} \ m o d 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

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

08:17 Uhr, 01.05.2015

Wenn die doppelte Hochzahl stört, beginne einfach mit

3^{2014}

.
Die Zahl

98

als

2 \cdot 7^{2}

zu schreiben war richig.
Jetzt ist Euler-Fermat an der Reihe, in diesem Fall ist es

3^{φ (n)} = 1

mod

n

.
Für

n

musst Du einmal

2

und einmal

7^{2}

nehmen. Da

φ (2) = 1

und

φ (7^{2}) = 7^{2} - 7 = 42

(siehe hier die Formel für

φ (p^{k})

für eine Primzahl

p

: de.wikipedia.org/wiki/Eulersche_Phi-Funktion, gibt Euler-Fermat:

3 = 1

mod

2

(das war auch ohne Satz klar) und

3^{42} = 1

mod

49

.
Jetzt den Chinesischen Restsatz anwenden, es folgt

3^{42} = 1

mod

98

. (In diesem Fall wäre es auch ohne diesen Satz möglich, es reicht, dass

3^{42}

ungerade ist).
Nun kannst Du

2014

durch

42

mit dem Rest teilen:

2014 = 47 \cdot 42 + 40

, daher

3^{2014} = (3^{42})^{47} \cdot 3^{40} = 1 \cdot 3^{40} = 3^{40}

mod

98

.
Und jetzt kann man auch die 2. Potenz behandeln:

(3^{2014})^{2014} = (3^{40})^{2014} = 3^{80560}

mod

98

.
Und da

80560 = 1918 \cdot 42 + 4

, haben

(3^{2014})^{2014} = 3^{80560} = (3^{42})^{1918} \cdot 3^{4} = 3^{4} = 81

mod

98

.

Vermutlich gib't auch eine elegantere Lösung, aber solange keine andere vorgeschlagen wird, vielleicht reicht auch diese.

DiMaGuy aktiv_icon

18:45 Uhr, 01.05.2015

Wegen der Klammer, in der Angabe steht es so:

Und laut WA kommt dein Ergebnis bei der anderen Version hinaus:
http//www.wolframalpha.com/input/?i=%283%5E2014%29%5E2014+mod+98
http//www.wolframalpha.com/input/?i=3%5E2014%5E2014+mod+98

DiMaGuy aktiv_icon

20:35 Uhr, 01.05.2015

Hier ein Thread mit mehr Antworten zu dieser Aufgabe:

http//www.matheboard.de/thread.php?postid=1984823

1231614

1231439

	Status: nicht eingeloggt	Noch nicht registriert?