Satz von Euler-Fermat: [3]²⁰¹⁴^2014 mod 98

2,3k 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⁴⁰ mod 49 kann ich den Satz von EF nicht noch einmal anwenden. Und im Kopf kann ich es auch nicht.