Eine Verallgemeinerung von Fermats Ergebnis: Für eine ganze Zahl n≥1 und a mit gcd(a,n)=1 gilt a^{φ(n)} ≡ 1 (mod n), wobei φ(n) Eulers Totientfunktion ist, die die Einheiten modulo n zählt.

Prinzip

Die multiplikative Gruppe der Einheiten modulo n hat die Ordnung φ(n); nach Lagranges Satz hat jedes Gruppenmitglied die Eigenschaft, dass seine Potenz φ(n) das Einselement ergibt, daher die Kongruenz a^{φ(n)} ≡ 1 (mod n).

Demonstration

Für n=10 ist φ(10)=4; für a=3 (teilerfremd zu 10) gilt 3^4=81 und 81 ≡ 1 (mod 10), ein einfaches Beispiel für einen zusammengesetzten Modulus.

Fehlanwendung

Die Kongruenz anwenden, wenn gcd(a,n)≠1 oder annehmen, φ(n) sei das minimale Exponent für alle Einheiten; in vielen Fällen ist der wahre Exponent ein echter Teiler von φ(n) (Carmichael-Phänomene).

Konsequenz

Ermöglicht die Reduktion von Exponenten in modularer Arithmetik für zusammengesetzte Module, bildet die Grundlage für RSA-ähnliche Konzepte (Exponenten-Arithmetik bezogen auf φ(n)) und rechtfertigt die Berechnung modularer Inverser durch Potenzierung, wenn Modul und Basis teilerfremd sind.

Umkehrung

Das Ersetzen von φ(n) durch kleinere universelle Exponenten (Carmichael λ(n)) oder die Suche nach Umkehrungen zeigt Grenzen: a^{φ(n)} ≡ 1 impliziert nicht die Primalität von n; die Untersuchung führt zu stärkeren Primalitätstests.

Abgrenzung

Voraussetzung ist, dass a eine Einheit modulo n ist und n eine positive ganze Zahl; gilt nicht direkt für Nicht-Einheiten oder für Moduli mit zusätzlicher algebraischer Struktur ohne Anpassung.

Semantische Spannung

Spannung zwischen Eulers allgemeiner Aussage und schärferen Exponenten wie der Carmichael-Funktion; auch Spannung mit praktischen Algorithmen, die kleinere Exponenten für Effizienz nutzen, oder mit speziellen Gruppenstrukturen (zyklisch vs. nichtzyklisch).

Synthese

Eulers Theorem abstrahiert Fermats Beobachtung auf die gesamte Einheitengruppe modulo n: die endliche Ordnung φ(n) liefert Potenzkongruenzen, die die modulare Arithmetik strukturieren und algorithmische Zahlentheorie informieren.