Die Sätze von Euler und Fermat
Wir können nun die ersten „großen Sätze“ über Kongruenzen zeigen. Wir beginnen mit:
Satz (Satz von Euler)
Sei m ≥ 1, und sei a teilerfremd zu m. Dann gilt aφ(m) ≡ 1 mod(m).
Beweis
Seien wieder 1 = r1 < … < rφ(m) ≤ m die zu m teilerfremden Zahlen zwischen 1 und m. Nach dem Umordnungssatz für Reste gilt
r1 · r2 · … · rφ(m) ≡ ar1 · ar2 · … · arφ(m) (m).
Die Zusammenfassung der a-Faktoren auf der rechten Seite liefert
r1 · r2 · … · rφ(m) ≡ aφ(m) r1 · r2 · … · rφ(m) (m).
Da alle Zahlen r1, …, rφ(m) teilerfremd zu m sind, können wir sie nach der Kürzungsregel alle kürzen, sodass
1 ≡ aφ(m) (m).
Beispielsweise gilt 34 ≡ 1 (10), da φ(10) = 4 und (3, 10) = 1. Nachrechnen zeigt, dass 34 = 81 ≡ 1 (10).
Aus dem Satz von Euler ergeben sich zahlreiche weitere Ergebnisse. Eines davon ist:
Korollar (Satz von Fermat)
Sei p prim, und sei a kein Vielfaches von p. Dann gilt ap − 1 ≡ 1 mod(p).
Beweis
Da a kein Vielfaches von p und p eine Primzahl ist, sind a und p teilerfremd. Wegen φ(p) = p − 1 ergibt sich die Aussage aus dem Satz von Euler.
Der Satz von Fermat ist also der Spezialfall des Satzes von Euler für einen Primzahlmodul.
Bemerkung
Oft wird der Satz von Fermat auch so formuliert:
Für alle Primzahlen p und alle ganzen Zahlen a ist ap ≡ a (p).
Diese Formulierung ist äquivalent zur Formulierung des Korollars: Denn ist a ein Vielfaches von p, so ist ap ≡ 0 ≡ a (p). Sei also a kein Vielfaches von p. Dann gehen die Kongruenzen der beiden Versionen durch Multiplikation mit a bzw. Kürzen von a ineinander über.
Tabelle der Potenzen ak modulo 10 für a, k = 0, …, 9; φ(10) = 4
Tabelle der Potenzen ak modulo 11 für a, k = 0, …, 10; φ(11) = 10
Tabelle der Potenzen ak modulo 22 für a, k = 0, …, 21; φ(22) = 10
Die Tabellen besitzen zahlreiche interessante Eigenschaften und der Leser mag versuchen, einige Hypothesen zu formulieren und zu beweisen. Die Potenzbildung ak modulo m wirft zudem sehr schwierige Fragen auf. Wir betrachten hierzu die auf der Menge { p | p prim, p ≠ 2, 5 } definierte Funktion f mit
f (p) = „das kleinste k ≥ 1 mit 10k ≡ 1 mod(p)“ für alle Primzahlen p ≠ 2, 5.
Die Zahl f (p) ist die Länge einer Minimalperiode der Dezimalbruchentwicklung von 1/p (Übung). Zum Beispiel ist
| 1/7 | = 0,1428571 | f (7) = 6 |
| 1/11 | = 0,09 | f (11) = 2 |
| 1/17 | = 0,0588235294117647 | f (17) = 16 |
Es ist ein offenes Problem, ob es unendlich viele Primzahlen p mit der Eigenschaft f (p) = p − 1 gibt. Die ersten p mit ultralangen Perioden sind
7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193
Tabelle der Potenzen ak modulo 23 für a, k = 0, …, 22; φ(23) = 22
Werte der Funktion g mit g(n) = mink ≥ 1 (10k ≡ 1 (pn)) mit der n-ten Primzahl pn ≠ 2, 5. Stellen n mit g(n) = pn − 1 sind rot markiert.