Euler'sche Phi-Funktion
Wie viele Zahlen von 1 bis 12 haben mit der 12 keinen gemeinsamen Teiler (außer 1 )? Durchzählen: 1, 5, 7, 11 – also 4 Stück. Diese Anzahl braucht man in der Zahlentheorie ständig: Sie sagt, wie viele Prime Restklassen|prime Restklassen es modulo 12 gibt, und sie steckt im Satz von Euler-Fermat und in der RSA-Verschlüsselung. Leonhard Euler hat ihr im 18. Jahrhundert einen eigenen Namen gegeben: die Phi-Funktion varphi . Bei großen Zahlen will man nicht durchzählen – zum Glück gibt es eine Formel. Definition varphi(n) ist die Anzahl der natürlichen Zahlen von 1 bis n , die zu n Teilerfremdheit|teilerfremd sind: varphi(n) = text{Anzahl der } k in {1, dots, n } text{ mit } text{ggT}(k, n) = 1 Selbst draufkommen am Beispiel n = 12 = 2^2 cdot 3 : - Jede zweite Zahl ist durch 2 teilbar → es bleibt die Hälfte: 12 cdot left(1 - frac{1}{2} right) = 6 - Davon ist jede dritte durch 3 teilbar → es bleiben zwei Drittel: 6 cdot left(1 - frac{1}{3} right) = 4 ✓ Formel: Hat n die verschiedenen Primfaktoren p 1, p 2, dots, p k (aus der Primfaktorzerlegung ), dann gilt varphi(n) = n cdot left(1 - frac{1}{p 1} right) cdot left(1 - frac{1}{p 2} right) cdot ldots cdot left(1 - frac{1}{p k} right) Jeder Primfaktor zählt nur einmal , egal mit welcher Hochzahl er vorkommt. Wichtige Spezialfälle - p Primzahl: varphi(p) = p - 1 (alle Zahlen außer p selbst) - p, q verschiedene Primzahlen: varphi(p cdot q) = (p - 1) cdot (q - 1) Berechne varphi(7) und varphi(10) . 7 ist eine Primzahl: varphi(7) = 7 - 1
Worum geht's?
Formel mit Erklärung
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
