Eulersche Totientfunktion berechnen

Die Eulersche Totientfunktion φ(n) zählt die positiven ganzen Zahlen von 1 bis n, die zu n teilerfremd sind. Für φ(10) gilt zum Beispiel 4, weil nur 1, 3, 7 und 9 keinen gemeinsamen Teiler größer als 1 mit 10 haben. Für φ(1) gilt nach Konvention der Wert 1.

Schreibe n als Produkt von Primzahlpotenzen. Dann gilt das Euler-Produkt φ(n) = n × Produkt aus (1 − 1/p) über alle verschiedenen Primfaktoren p. Der Rechner zerlegt n zuerst in Primfaktoren und verwendet anschließend eine ganzzahlige Form der Formel, damit das Ergebnis exakt bleibt.

Die Zahl 36 hat die Primfaktorzerlegung 2² × 3². Deshalb gilt φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 12. Genau 12 Zahlen von 1 bis 36 sind zu 36 teilerfremd. Die teilerfremde Dichte beträgt 12/36, also ungefähr 33,33 %.

Eine Primzahl p hat außer 1 und p keine positiven Teiler. Deshalb sind alle Zahlen von 1 bis p − 1 zu p teilerfremd. Es gibt genau p − 1 solcher Zahlen. Der Rechner erkennt Primzahlen und zeigt diese Eigenschaft in der Ergebnisbeschreibung an.

Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist. Für teilerfremde Zahlen m und n gilt φ(m × n) = φ(m) × φ(n). Diese Multiplikativität erklärt, warum die Funktion aus den verschiedenen Primfaktoren der Eingabe aufgebaut werden kann.

Die Totientfunktion ist eine Grundlage des Satzes von Euler und spielt eine wichtige Rolle in der modularen Arithmetik. Sie wird auch bei der Konstruktion von RSA-Schlüsseln verwendet. Der Rechner erklärt die zugrunde liegende Zahlentheorie, ersetzt aber keine sichere Kryptografiebibliothek.