Eulersche-Phi-Funktion-Rechner

Ermitteln Sie die Phi-Funktion von Euler für jede positive ganze Zahl.

So wird gerechnet

Eulers Phi-Funktion φ(n) zählt die ganzen Zahlen von 1 bis n, die mit n keinen gemeinsamen Teiler außer 1 haben. Das Tool prüft nicht jede Zahl einzeln. Es zerlegt n in Primfaktoren und wendet die Produktformel φ(n) = n × ∏(1 − 1/p) über jede verschiedene Primzahl p an, die n teilt, und verwendet dabei nur ganzzahlige Schritte. Für eine Primzahl p gilt φ(p) = p − 1. Die Eingabe muss eine ganze Zahl von 1 bis 1.000.000.000 sein; eine Dezimalzahl wie 36,5 liefert kein Ergebnis. Beide Ergebnisfelder zeigen dieselbe Anzahl.

Rechenbeispiel

Nehmen wir n = 36. Die Primfaktoren sind 2 und 3, denn 36 = 2² × 3². Beginnen Sie mit 36. Für die Primzahl 2 ziehen Sie 36 / 2 = 18 ab, es bleiben 18. Für die Primzahl 3 ziehen Sie 18 / 3 = 6 ab, es bleiben 12. Also ist φ(36) = 12: Die Zahlen 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 und 35 haben keinen gemeinsamen Teiler mit 36.

Dieses Beispiel ausprobieren →

Häufige Fehler

  • Jeden Primfaktor mit seiner Vielfachheit zählen. 36 = 2 × 2 × 3 × 3 verwendet in der Formel nur die verschiedenen Primzahlen 2 und 3.
  • Annehmen, dass φ(n) = n − 1 für jedes n gilt. Das trifft nur auf Primzahlen zu; für 36 ist es 12, nicht 35.
  • φ-Werte von Zahlen multiplizieren, die gemeinsame Teiler haben. φ(a × b) = φ(a) × φ(b) gilt nur, wenn a und b teilerfremd sind.
  • Eine Dezimalzahl oder eine Zahl über einer Milliarde eingeben. Eine Dezimalzahl oder ein größerer Wert liefert kein Ergebnis.

Quellen

Über diesen Rechner

Dieser Rechner ermittelt Eulers Phi-Funktion φ(n) – die Anzahl der positiven ganzen Zahlen von 1 bis n, die zu n teilerfremd sind (keinen gemeinsamen Teiler mit n außer 1 haben). Sie wird aus der Primfaktorzerlegung von n mit der Produktformel φ(n) = n·∏(1 − 1/p) über jeden verschiedenen Primfaktor p von n berechnet; für eine Primzahl p selbst gilt φ(p) = p − 1.

Die Phi-Funktion ist zentral für die Zahlentheorie und die mathematische Grundlage des RSA-Public-Key-Kryptosystems, bei dem φ(n) (berechnet aus zwei großen geheimen Primzahlen) verwendet wird, um den privaten Schlüssel aus dem öffentlichen Schlüssel abzuleiten. Sie bestimmt auch den Satz von Euler, eine Verallgemeinerung des kleinen Satzes von Fermat, der in der gesamten modularen Arithmetik verwendet wird.

War das hilfreich?

Sie können bis zu 3 Reaktionen auswählen.

Kommentare

  • Schreiben Sie den ersten Kommentar.

Beliebte Rechner

Alle Rechner