Die eulersche Phi-Funktion erklärt
Schreiben Sie die Zahlen von 1 bis 10 auf und streichen Sie jede, die einen Teiler mit 10 gemeinsam hat. Vier bleiben übrig: 1, 3, 7 und 9. Diese Anzahl, φ(10) = 4, ist die eulersche Phi-Funktion, eine der meistgenutzten Funktionen der Zahlentheorie, von Brüchen und Uhren bis zur Verschlüsselung, die Onlinezahlungen schützt.
Teilerfremde Zahlen zählen
Zwei Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist. φ(n) zählt die k von 1 bis n mit ggT(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 und φ(1) = 1. Dieselbe Anzahl taucht an vielen Stellen auf. Sie ist die Anzahl der Brüche k/n zwischen 0 und 1, die bereits vollständig gekürzt sind, die Anzahl der Schrittweiten, mit denen ein Zeiger auf einer Uhr mit n Stunden jede Stunde erreicht, und die Anzahl der k, die ein Inverses mod n haben, sodass sich k × x ≡ 1 (mod n) lösen lässt.
Die Produktformel
Sind p₁, p₂ … die Primzahlen, die n teilen, dann ist φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Der Grund ist ein Sieb. Die Hälfte aller Zahlen ist gerade, das Streichen der Vielfachen von 2 lässt also den Anteil 1 − 1/2 übrig; von den übrigen Zahlen ist jede dritte ein Vielfaches von 3, und so weiter. Nach dem chinesischen Restsatz sind die Bedingungen für verschiedene Primzahlen unabhängig, sodass sich die Anteile einfach multiplizieren. Für 100 = 2² × 5² ergibt das 100 × 1/2 × 4/5 = 40. Zwei Tatsachen liefern dasselbe Ergebnis in anderer Form: φ(p^k) = p^(k−1)(p − 1) und φ(mn) = φ(m) φ(n) für teilerfremde m und n, also φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Der Satz von Euler
Fermat bemerkte 1640, dass a^(p−1) ≡ 1 (mod p) für eine Primzahl p und jedes a gilt, das nicht durch p teilbar ist. Euler bewies die allgemeine Form, veröffentlicht 1763: a^φ(n) ≡ 1 (mod n), wann immer ggT(a, n) = 1. Der Beweis ist kurz. Multipliziert man die φ(n) zu n teilerfremden Zahlen mit a, so sind die Produkte wieder teilerfremd zu n und mod n alle verschieden, also dieselben Zahlen in anderer Reihenfolge, und der Vergleich der beiden Produkte lässt a^φ(n) ≡ 1 übrig. Der kleinste Exponent, der für ein bestimmtes a funktioniert, ist seine Ordnung, die stets φ(n) teilt; der kleinste, der für alle a zugleich funktioniert, ist die Carmichael-Funktion λ(n). Für 561 = 3 × 11 × 17 teilt λ(561) = 80 die Zahl 560, also gilt a^560 ≡ 1 (mod 561) für jedes zu 561 teilerfremde a, obwohl 561 keine Primzahl ist. Sie ist die kleinste Carmichael-Zahl und der Grund, warum der Fermat-Test allein nicht beweisen kann, dass eine Zahl prim ist.
Die Teilersumme von Gauß und der Mittelwert
Addiert man φ(d) über die Teiler d von n, erhält man immer n zurück: für 12 ist φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauß bewies das 1801 in seinen Disquisitiones Arithmeticae; man sieht es, wenn man die Brüche 1/12, 2/12 … 12/12 vollständig kürzt und nach ihren Nennern sortiert. Im Mittel ist φ(k) etwa 0,61 k: Der Mittelwert von φ(k)/k strebt gegen 6/π² ≈ 0,6079, was zugleich die Wahrscheinlichkeit ist, dass zwei zufällige ganze Zahlen teilerfremd sind, und φ(1) + … + φ(N) liegt nahe bei 3N²/π². Für N = 1.000 ist die Summe 304.192, gegenüber 3N²/π² ≈ 303.964.
Werte, die nie vorkommen
φ(n) ist für jedes n ab 3 gerade, denn die zu n teilerfremden Zahlen treten paarweise als k und n − k auf. Auch nicht jede gerade Zahl ist ein Wert: 14, 26, 34, 38 und 50 sind die ersten, die nie vorkommen, während 24 der Wert von zehn verschiedenen Zahlen ist, von 35 bis 90. Sie zu finden ist eine endliche Suche, denn für jede Primzahl p, die n teilt, muss p − 1 ein Teiler von φ(n) sein. 1907 behauptete Robert Carmichael, dass kein Wert genau einmal angenommen wird. Sein Beweis war falsch, die Behauptung ist weiter offen, und jede Ausnahme müsste größer als 10^(10^10) sein. D. H. Lehmer fragte 1932, ob φ(n) für ein zusammengesetztes n ein Teiler von n − 1 sein kann; kein Beispiel ist bekannt.
Die Phi-Funktion bei RSA
RSA wählt zwei große Primzahlen p und q und veröffentlicht n = pq und einen Exponenten e. Da φ(n) = (p − 1)(q − 1), kann jeder, der n zerlegen kann, φ(n) berechnen und daraus den privaten Exponenten d mit e × d ≡ 1 (mod φ(n)); der Satz von Euler sorgt dann für (m^e)^d ≡ m (mod n). Im Lehrbuchbeispiel n = 3233 = 61 × 53 ist φ(n) = 3.120, e = 17 und d = 2.753. Viele Implementierungen verwenden stattdessen λ(n) = kgV(p − 1, q − 1), hier 780, was das kleinere d = 413 ergibt. φ(n) für einen RSA-Modul mit 600 Stellen zu berechnen ist so schwer, wie ihn zu zerlegen: Aus n und φ(n) folgen die beiden Primzahlen mit einer einzigen Quadratwurzel.
Selbst ausprobieren
Öffnen Sie den Rechner und geben Sie ein beliebiges n bis 10^18 ein, um φ(n) mit den Primfaktoren und der Formel zu sehen. Bis 500 werden die Zahlen 1 bis n gezeichnet, die teilerfremden ausgefüllt und die anderen in der Farbe der kleinsten Primzahl, die sie mit n teilen, sodass die Produktformel zu einem Sieb wird, das man nachzählen kann. Wählen Sie eine Zahl a, um den Satz von Euler zu prüfen, wechseln Sie zu Diagramm, um φ(k) bis 100.000 mit den Primzahlen auf der Geraden φ(p) = p − 1 zu sehen, oder zu Umkehrung, um jedes n mit φ(n) = m zu finden.
Häufig gestellte Fragen
Warum ist φ(1) = 1?
Weil ggT(1, 1) = 1: Die einzige Zahl von 1 bis 1 ist zu 1 teilerfremd. Die Konvention hält auch die Formeln gültig, etwa die Summe von Gauß über die Teiler von n, die für n = 1 einfach φ(1) = 1 ist.
Ist φ dasselbe wie die Primzahlfunktion?
Nein. π(n) zählt die Primzahlen bis n, φ(n) die Zahlen bis n, die zu n teilerfremd sind. φ(10) = 4 zählt 1, 3, 7 und 9, während π(10) = 4 die Zahlen 2, 3, 5 und 7 zählt. Dass sie hier übereinstimmen, ist Zufall: φ(12) = 4, aber π(12) = 5.
Wie schnell lässt sich φ(n) berechnen?
So schnell, wie sich n zerlegen lässt. Mit bekannten Primfaktoren sind es ein paar Multiplikationen; ohne sie ist kein schnelles Verfahren bekannt, und genau darauf beruht RSA. Für Zahlen bis 10^18 dauert die Zerlegung im Browser Millisekunden, für Zahlen mit Hunderten von Stellen kann sie Jahre dauern.
Welche Zahlen haben das kleinste φ(n) im Verhältnis zu n?
Zahlen mit vielen kleinen Primfaktoren. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… hängt nur davon ab, welche Primzahlen n teilen, nicht von ihren Potenzen: Für jede Zweierpotenz ist es genau 1/2, und für 30 = 2 × 3 × 5 ist es 8/30, etwa 27 %. Das Produkt der ersten 15 Primzahlen, 614.889.782.588.491.410, hat φ(n)/n ≈ 14 %, den kleinsten Wert aller Zahlen bis 10^18.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Phi-Rechner öffnen