Euler-Funktion φ(n)

Wofür Euler-Funktion φ(n) gedacht ist

φ(n) zählt, wie viele ganze Zahlen zwischen 1 und n zu n teilerfremd sind – also keinen gemeinsamen Teiler außer 1 mit n haben. Gerechnet wird über die Primfaktorzerlegung: φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · … über alle verschiedenen Primteiler p. Das bekannte Beispiel φ(12) = 4, denn teilerfremd zu 22 sind nur 1, 5, 7 und 11. Rechenweg zum Mitnehmen: φ(p) = p−1 für eine Primzahl p und φ(p·q) = (p−1)(q−1) für zwei verschiedene Primzahlen.

Bedienung

Eine ganze Zahl ab 1 eintippen.
„Berechnen“ klicken und Primfaktorzerlegung sowie φ(n) ablesen – die Formel gleich am Beispiel mitprüfen.

Typische Anwendungen: Zahlentheorie: Teilerfremdheit und Gruppen verstehen., Kryptografie: Den Hintergrund von RSA nachvollziehen., Schule: Mit Primfaktoren und φ(n) üben..

Fragen und Antworten

Was bedeutet φ(n)?

Es zählt die Zahlen zwischen 1 und n, die zu n teilerfremd sind.

Wie lautet die Formel?

φ(n) = n · ∏ (1 − 1/p) über alle Primteiler p.

Wie viel ist φ(12)?

Wofür steht RSA?

Ein asymmetrisches Verfahren, das auf der Euler-Funktion aufbaut.

Einschränkungen

Die Zahl wird vollständig faktorisiert; bei sehr großen Werten kann die Rechnung spürbar dauern.

Was das Werkzeug kann

Ganze Zahl n eingeben, Wert φ(n) als Ergebnis, Vollständige Primfaktorzerlegung, Anzeige der Produktformel, Auch für größere Zahlen geeignet, Sofortiges Ergebnis, Klares Zahlenbeispiel im Ergebnis

Diese Werkzeuge passen:

🔢

Primzahlen, ggT und Wurzeln

Primzahltest, Primzahlenlisten, Primfaktorzerlegung, größter gemeinsamer Teiler, kleinstes gemeinsames Vielfaches und vereinfachte Wurzeln – mit Teilern.

›

🔣

Mengenoperationen

Die Mengenoperationen Vereinigung ∪, Schnitt ∩, Differenz A∖B und symmetrische Differenz auf zwei eigene Wertemengen ausführen.

›

🧮

Kombinatorik

Die Kombinationsanzahl C(n,k) = n! / (k!·(n−k)!) ohne Zurücklegen und ohne Reihenfolge berechnen – für Lotto, Statistik und Wahrscheinlichkeitsrechnung.

›