φ(n)
Primfaktoren
Anteil teilerfremd
Teiler

          Anzeigen

          Mehr über die eulersche Phi-Funktion

          Rechner für die eulersche Phi-Funktion

          Von den Zahlen 1 bis 12 haben nur 1, 5, 7 und 11 keinen gemeinsamen Teiler mit 12, also ist φ(12) = 4. Die eulersche Phi-Funktion zählt diese teilerfremden Zahlen für jedes n. Geben Sie eine Zahl bis 10^18 ein und erhalten Sie φ(n) mit den Primfaktoren und der ausgeschriebenen Produktformel, sehen Sie die Zahlen 1 bis n mit den teilerfremden hervorgehoben, prüfen Sie den Satz von Euler, zeichnen Sie φ(k) für bis zu 100.000 Zahlen auf einmal oder finden Sie jedes n mit einem gegebenen φ(n). Geben Sie eine ganze Zahl n bis 10^18 ein oder wählen Sie ein Rechenbeispiel. Die Kacheln zeigen φ(n), die Primfaktoren von n, den Anteil der Zahlen von 1 bis n, die zu n teilerfremd sind, und die Anzahl der Teiler; die Schritte schreiben die Produktformel mit Ihren Zahlen aus. Bis n = 500 werden die Zahlen 1 bis n gezeichnet: Die teilerfremden sind ausgefüllt, die anderen in der Farbe der kleinsten Primzahl, die sie mit n gemeinsam haben. Zeigen Sie auf eine Zahl, um ihren ggT mit n zu sehen, und klicken Sie darauf, um sie als a im Satz von Euler zu verwenden. Diagramm zeigt φ(k) für jedes k bis zu einer Grenze; klicken Sie auf einen Punkt, um diese Zahl zu öffnen. Umkehrung listet jedes n mit φ(n) = m auf; klicken Sie auf eines, um es zu öffnen.

          Wie es funktioniert

          1. Geben Sie eine ganze Zahl n bis 10^18 ein oder wählen Sie ein Rechenbeispiel wie φ(60), einen RSA-Modul oder die Carmichael-Zahl 561.
          2. Lesen Sie φ(n), die Primfaktoren und die Produktformel mit Ihren Zahlen ab. Zeigen Sie bis 500 auf die Zahlen 1 bis n, um ihren ggT mit n zu sehen, und klicken Sie auf eine, um damit den Satz von Euler zu prüfen.
          3. Wechseln Sie zu Diagramm, um φ(k) für jedes k bis 100.000 zu sehen, oder zu Umkehrung, um jedes n mit φ(n) = m aufzulisten.

          Wie φ(n) berechnet wird

          Zerlegen Sie n in Primfaktoren und multiplizieren Sie n für jede Primzahl p, die n teilt, mit (1 − 1/p). Für 60 = 2² × 3 × 5 ergibt das 60 × 1/2 × 2/3 × 4/5 = 16. Streichen liefert dieselbe Anzahl: Von den 60 Zahlen sind 30 gerade; von den 30 ungeraden sind 10 Vielfache von 3; von den 20 übrigen sind 4 Vielfache von 5, und es bleiben 16. Für Primzahlpotenzen lautet die Formel φ(p^k) = p^(k−1)(p − 1), und die Werte werden multipliziert: φ(60) = 2 × 2 × 4. Schwierig ist die Zerlegung. Der Rechner nutzt Probedivision, einen Miller-Rabin-Primzahltest und Pollards Rho-Methode, sodass selbst ein 18-stelliges Produkt zweier 9-stelliger Primzahlen nur Bruchteile einer Sekunde dauert.

          Wo die Phi-Funktion gebraucht wird

          φ(n) zählt die Brüche k/n zwischen 0 und 1, die bereits vollständig gekürzt sind, die Schrittweiten, mit denen ein Zeiger auf einer Uhr mit n Stunden jede Stunde erreicht (1, 5, 7 und 11 auf einer 12-Stunden-Uhr), und die Zahlen, die ein Inverses mod n haben. Euler bewies, dass a^φ(n) ≡ 1 (mod n) für jedes zu n teilerfremde a gilt, und die RSA-Verschlüsselung beruht darauf: Mit n = 3233 = 61 × 53 ist φ(n) = 60 × 52 = 3.120, und der öffentliche Exponent 17 hat den privaten Partner 2.753, denn 17 × 2.753 = 15 × 3.120 + 1.

          Häufig gestellte Fragen

          Was ist die eulersche Phi-Funktion?

          φ(n) ist die Anzahl der ganzen Zahlen von 1 bis n, die mit n keinen gemeinsamen Teiler außer 1 haben. φ(9) = 6, denn 1, 2, 4, 5, 7 und 8 sind zu 9 teilerfremd, während 3, 6 und 9 den Teiler 3 mit 9 teilen. Per Konvention ist φ(1) = 1. Euler untersuchte die Funktion in den 1760er-Jahren; Gauß gab ihr 1801 das Zeichen φ, und James Joseph Sylvester 1879 den englischen Namen totient.

          Was ist φ einer Primzahl?

          p − 1, denn jede Zahl von 1 bis p − 1 ist zu einer Primzahl p teilerfremd, also φ(97) = 96. Für eine Primzahlpotenz gilt φ(p^k) = p^k − p^(k−1), denn nur die Vielfachen von p haben mit ihr einen gemeinsamen Teiler: φ(81) = 81 − 27 = 54.

          Was besagt der Satz von Euler?

          Sind a und n teilerfremd, dann lässt a^φ(n) bei Division durch n den Rest 1. Für n = 60 und a = 7: φ(60) = 16, und 7^16 ≡ 1 (mod 60). Der kleine fermatsche Satz ist der Fall einer Primzahl n. Oft reicht schon ein kleinerer Exponent: 7^4 = 2.401 = 40 × 60 + 1. Der kleinste Exponent, der für jedes zu n teilerfremde a funktioniert, ist die Carmichael-Funktion λ(n), für 60 ist sie 4.

          Können zwei Zahlen dieselbe Phi-Funktion haben?

          Ja, und meist sind es mehrere: φ(n) = 24 für n = 35, 39, 45, 52, 56, 70, 72, 78, 84 und 90. Manche geraden Zahlen kommen als Wert nie vor, die kleinste ist 14, und keine ungerade Zahl über 1 kommt vor, denn φ(n) ist ab n = 3 gerade. Robert Carmichael behauptete 1907, dass kein Wert genau einmal angenommen wird. Das ist bis heute unbewiesen, und Kevin Ford zeigte 1998, dass eine Ausnahme größer als 10^(10^10) sein müsste.

          Wie große Zahlen kann ich eingeben?

          Jede ganze Zahl bis 10^18. Der Rechner zerlegt sie mit exakter Ganzzahlarithmetik in Ihrem Browser, sodass φ(10^18) = 4 × 10^17 und φ(999.999.866.000.004.473) = 999.999.864.000.004.608 bis zur letzten Stelle stimmen. Die Zahlen 1 bis n werden bis 500 gezeichnet, das Diagramm reicht bis 100.000 und die Umkehrung funktioniert für Werte bis 10^10.

          Bereit, es auszuprobieren?

          Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

          Zum Editor