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?

Wie viele Zahlen von 1 1 1 bis 12 12 12 haben mit der 12 12 12 keinen gemeinsamen Teiler (außer 1 1 1 )? Durchzählen: 1 , 5 , 7 , 11 1, 5, 7, 11 1 , 5 , 7 , 11 – also 4 4 4 Stück. Diese Anzahl braucht man in der Zahlentheorie ständig: Sie sagt, wie viele prime Restklassen es modulo 12 12 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.

Formel mit Erklärung

Definition φ ( n ) \varphi(n) φ ( n ) ist die Anzahl der natürlichen Zahlen von 1 1 1 bis n n n , die zu n n n teilerfremd sind: φ ( n ) = Anzahl der  k ∈ { 1 , … , n }  mit ggT ( k , n ) = 1 \varphi(n) = \text{Anzahl der } k \in \{1, \dots, n\} \text{ mit } \text{ggT}(k, n) = 1 φ ( n ) = Anzahl der  k ∈ { 1 , … , n }  mit  ggT ( k , n ) = 1 Selbst draufkommen am Beispiel n = 12 = 2 2 ⋅ 3 n = 12 = 2^2 \cdot 3 n = 12 = 2 2 ⋅ 3 : Jede zweite Zahl ist durch 2 2 2 teilbar → es bleibt die Hälfte: 12 ⋅ ( 1 − 1 2 ) = 6 12 \cdot \left(1 - \frac{1}{2}\right) = 6 12 ⋅ ( 1 − 2 1 ​ ) = 6 Davon ist jede dritte durch 3 3 3 teilbar → es bleiben zwei Drittel: 6 ⋅ ( 1 − 1 3 ) = 4 6 \cdot \left(1 - \frac{1}{3}\right) = 4 6 ⋅ ( 1 − 3 1 ​ ) = 4 ✓ Formel: Hat n n n die verschiedenen Primfaktoren p 1 , p 2 , … , p k p_1, p_2, \dots, p_k p 1 ​ , p 2 ​ , … , p k ​ (aus der Primfaktorzerlegung ), dann gilt φ ( n ) = n ⋅ ( 1 − 1 p 1 ) ⋅ ( 1 − 1 p 2 ) ⋅ … ⋅ ( 1 − 1 p k ) \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) φ ( n ) = n ⋅ ( 1 − p 1 ​ 1 ​ ) ⋅ ( 1 − p 2 ​ 1 ​ ) ⋅ … ⋅ ( 1 − p k ​ 1 ​ ) Jeder Primfaktor zählt nur einmal , egal mit welcher Hochzahl er vorkommt. Wichtige Spezialfälle p p p Primzahl: φ ( p ) = p − 1 \varphi(p) = p - 1 φ ( p ) = p − 1 (alle Zahlen außer p p p selbst) p , q p, q p , q verschiedene Primzahlen: φ ( p ⋅ q ) = ( p − 1 ) ⋅ ( q − 1 ) \varphi(p \cdot q) = (p - 1) \cdot (q - 1) φ ( p ⋅ q ) = ( p − 1 ) ⋅ ( q − 1 )

Beispiele

Leicht#1
Berechne φ ( 7 ) \varphi(7) φ ( 7 ) und φ ( 10 ) \varphi(10) φ ( 10 ) . 7 7 7 ist eine Primzahl: φ ( 7 ) = 7 − 1 = 6 \varphi(7) = 7 - 1 = 6 φ ( 7 ) = 7 − 1 = 6 (die Zahlen 1 , 2 , 3 , 4 , 5 , 6 1, 2, 3, 4, 5, 6 1 , 2 , 3 , 4 , 5 , 6 ). 10 = 2 ⋅ 5 10 = 2 \cdot 5 10 = 2 ⋅ 5 : φ ( 10 ) = 10 ⋅ ( 1 − 1 2 ) ⋅ ( 1 − 1 5 ) = 10 ⋅ 1 2 ⋅ 4 5 = 4 \varphi(10) = 10 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) = 10 \cdot \frac{1}{2} \cdot \frac{4}{5} = 4 φ ( 10 ) = 10 ⋅ ( 1 − 2 1 ​ ) ⋅ ( 1 − 5 1 ​ ) = 10 ⋅ 2 1 ​ ⋅ 5 4 ​ = 4 Probe durch Zählen: 1 , 3 , 7 , 9 1, 3, 7, 9 1 , 3 , 7 , 9 ✓

Zusammenfassung

φ ( n ) \varphi(n) φ ( n ) zählt die Zahlen von 1 1 1 bis n n n , die zu n n n teilerfremd sind. Formel: φ ( n ) = n ⋅ ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p k ) \varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_k}\right) φ ( n ) = n ⋅ ( 1 − p 1 ​ 1 ​ ) ⋯ ( 1 − p k ​ 1 ​ ) über die verschiedenen Primfaktoren. Primzahl: φ ( p ) = p − 1 \varphi(p) = p - 1 φ ( p ) = p − 1 . Zwei Primzahlen: φ ( p ⋅ q ) = ( p − 1 ) ( q − 1 ) \varphi(p \cdot q) = (p - 1)(q - 1) φ ( p ⋅ q ) = ( p − 1 ) ( q − 1 ) . φ ( m ) \varphi(m) φ ( m ) ist die Anzahl der primen Restklassen modulo m m m .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: