Satz von Euler-Fermat

Welche Ziffer steht am Ende von 7^{20} ? Die Zahl hat 17 Stellen – ausrechnen will das keiner. Schauen wir auf die letzten Ziffern der Potenzen: | k | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| | 7^k | 7 | 49 | 343 | 2401 | 16807 | 117649 | | letzte Ziffer | 7 | 9 | 3 | 1 | 7 | 9 | Nach 4 Schritten kommt die 1 , danach wiederholt sich alles. Ist das Zufall? Nein! Der Satz von Euler-Fermat sagt vorher, wann spätestens die 1 kommt – ohne Probieren. Er ist das Herzstück der RSA-Verschlüsselung, mit der z. B. Online-Banking gesichert wird. Satz von Euler-Fermat Ist n eine natürliche Zahl und a eine ganze Zahl mit text{ggT}(a, n) = 1 , dann gilt a^{ varphi(n)} equiv 1 pmod{n} Dabei ist varphi die Euler'sche Phi-Funktion . In Worten: a^{ varphi(n)} lässt beim Teilen durch n den Rest 1 . Im Beispiel oben: varphi(10) = 4 , also 7^4 equiv 1 pmod{10} ✓ Sonderfall (kleiner Satz von Fermat): Ist n = p eine Primzahl und p nmid a , dann ist varphi(p) = p - 1 und a^{p - 1} equiv 1 pmod{p} Bedingung nicht vergessen: a und n müssen Teilerfremdheit|teilerfremd sein. Für a = 2 , n = 4 klappt es nicht: 2^{ varphi(4)} = 2^2 = 4 equiv 0 pmod 4 . So rechnet man große Potenzen aus Prüfe den kleinen Satz von Fermat für a = 2 und p = 5 . 2^{5 - 1} = 2^4 = 16 = 3 cdot 5 + 1 qquad Rightarrow qquad 2^4 equiv 1 pmod{5} ✓ Letzte Ziffer von 7^{20} Plan: Letzte Ziffer = Rest modulo 10 . - text{ggT}(7, 10) = 1 ✓ - varphi(10) = 4 - 20 = 5 cdot 4 + 0 7^{20} = left(7^4 right)^5 equiv 1^5 = 1 pmod{10}

Worum geht's?

Welche Ziffer steht am Ende von 7 20 7^{20} 7 20 ? Die Zahl hat 17 17 17 Stellen – ausrechnen will das keiner. Schauen wir auf die letzten Ziffern der Potenzen: k k k 1 2 3 4 5 6 7 k 7^k 7 k 7 49 343 2401 16807 117649 letzte Ziffer 7 9 3 1 7 9 Nach 4 4 4 Schritten kommt die 1 1 1 , danach wiederholt sich alles. Ist das Zufall? Nein! Der Satz von Euler-Fermat sagt vorher, wann spätestens die 1 1 1 kommt – ohne Probieren. Er ist das Herzstück der RSA-Verschlüsselung, mit der z. B. Online-Banking gesichert wird.

Formel mit Erklärung

Satz von Euler-Fermat Ist n n n eine natürliche Zahl und a a a eine ganze Zahl mit ggT ( a , n ) = 1 \text{ggT}(a, n) = 1 ggT ( a , n ) = 1 , dann gilt a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)} \equiv 1 \pmod{n} a φ ( n ) ≡ 1 ( mod n ) Dabei ist φ \varphi φ die Euler'sche Phi-Funktion . In Worten: a φ ( n ) a^{\varphi(n)} a φ ( n ) lässt beim Teilen durch n n n den Rest 1 1 1 . Im Beispiel oben: φ ( 10 ) = 4 \varphi(10) = 4 φ ( 10 ) = 4 , also 7 4 ≡ 1 ( m o d 10 ) 7^4 \equiv 1 \pmod{10} 7 4 ≡ 1 ( mod 10 ) ✓ Sonderfall (kleiner Satz von Fermat): Ist n = p n = p n = p eine Primzahl und p ∤ a p \nmid a p ∤ a , dann ist φ ( p ) = p − 1 \varphi(p) = p - 1 φ ( p ) = p − 1 und a p − 1 ≡ 1 ( m o d p ) a^{p - 1} \equiv 1 \pmod{p} a p − 1 ≡ 1 ( mod p ) Bedingung nicht vergessen: a a a und n n n müssen teilerfremd sein. Für a = 2 a = 2 a = 2 , n = 4 n = 4 n = 4 klappt es nicht: 2 φ ( 4 ) = 2 2 = 4 ≡ 0 ( m o d 4 ) 2^{\varphi(4)} = 2^2 = 4 \equiv 0 \pmod 4 2 φ ( 4 ) = 2 2 = 4 ≡ 0 ( mod 4 ) . So rechnet man große Potenzen aus
Rest von a hoch k modulo n
  1. 1
    Prüfen, ob ggT(a, n) = 1 ist.
  2. 2
    φ(n) berechnen.
  3. 3
    Die Hochzahl k durch φ(n) teilen: k = q · φ(n) + r.
  4. 4
    Danngiltak=(aφ(n))q⋅ar≡1q⋅ar=ar(modn).Dann gilt a^k = (a^φ(n))^q · a^r ≡ 1^q · a^r = a^r (mod n).
  5. 5
    Die kleine Potenz a^r ausrechnen und mod n nehmen.

Beispiele

Leicht#1
Prüfe den kleinen Satz von Fermat für a = 2 a = 2 a = 2 und p = 5 p = 5 p = 5 . 2 5 − 1 = 2 4 = 16 = 3 ⋅ 5 + 1 ⇒ 2 4 ≡ 1 ( m o d 5 )   ✓ 2^{5 - 1} = 2^4 = 16 = 3 \cdot 5 + 1 \qquad\Rightarrow\qquad 2^4 \equiv 1 \pmod{5}\ ✓ 2 5 − 1 = 2 4 = 16 = 3 ⋅ 5 + 1 ⇒ 2 4 ≡ 1 ( mod 5 )   ✓

Zusammenfassung

Satz von Euler-Fermat: Aus ggT ( a , n ) = 1 \text{ggT}(a, n) = 1 ggT ( a , n ) = 1 folgt a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)} \equiv 1 \pmod{n} a φ ( n ) ≡ 1 ( mod n ) . Für Primzahlen p p p (kleiner Fermat): a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod{p} a p − 1 ≡ 1 ( mod p ) , wenn p ∤ a p \nmid a p ∤ a . Große Potenzen: Hochzahl durch φ ( n ) \varphi(n) φ ( n ) teilen, nur der Rest der Hochzahl zählt. Ohne Teilerfremdheit gilt der Satz nicht. Anwendung: letzte Ziffern großer Potenzen, RSA-Verschlüsselung.

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: