## [Eulers Satz](/de/node/63494) Definition 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 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 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 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 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 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 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 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 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.