Eulersche Phi-Funktion

Die eulersche Phi-Funktion ist eine zahlentheoretische Funktion. Sie ordnet jeder natürlichen Zahl nn die Anzahl der natürlichen Zahlen aa von 1 bis nn zu, die zu nn teilerfremd sind, für die also ggT⁡(a,n)=1\ggT(a,n) = 1 ist.
Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben φ\phi (Phi) bezeichnet.

Beispiele

  • Die Zahl 6 ist zu zwei Zahlen zwischen 1 und 6 teilerfremd (1 und 5), also ist φ\phi(6) = 2.
  • Die Zahl 13 ist als Primzahl zu den zwölf Zahlen von 1 bis 12 teilerfremd, also ist φ\phi(13) = 12.
  • Die ersten 20 Werte der φ\phi-Funktion lauten:
    • n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    f(n)f(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8

Berechnung

Primzahlen

Da alle Primzahlen pp nur durch 1 und sich selbst teilbar sind, sind sie sicher zu den Zahlen 1 bis pp-1 teilerfremd, daher ist φ\phi(pp) = pp-1.

Potenz von Primzahlen

Eine Potenz pkp^{k} aus einer Primzahl pp und einer natürlichen Zahl kk ist nur zu Vielfachen von pp nicht teilerfremd. Es gibt pk−1p^{k-1} Vielfache von pp, die kleiner oder gleich pkp^{k} sind (1*pp, 2*pp, ..., pk−1p^{k-1}*pp). Daher gilt:
φ(pk)=pk−pk−1\varphi(p^k) = p^k-p^{k-1} =pk−1(p−1)=pk(1−1/p)= p^{k-1}(p-1)= p^{k}(1-1/p)
Beispiel
φ\phi(16) = φ(24)\phi(2^{4}) = 24−232^{4} - 2^{3} = 23∗(2−1)2^{3} * (2 - 1) = 242^{4} * (1-1/2) = 8 * 1 = 8

Multiplikativität

Die φ\phi-Funktion ist multiplikativ für teilerfremde natürliche Zahlen:
φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n), falls ggT⁡(m,n)=1\ggT(m, n) = 1
Beispiel:
φ\phi(18) = φ\phi(2)*φ\phi(9) = 1*6 = 6
Gegenbeispiel für Zahlen mm und nn mit gemeinsamem Primfaktor:
φ\phi(2*4) = φ\phi(8) = 4, aber φ\phi(2)*φ\phi(4) = 1*2 = 2.

Zusammengesetzte Zahlen

Die Berechnung von φ\phi(nn) für zusammengesetzte Zahlen nn ergibt sich aus der Multiplikativität. Hat nn die kanonische Darstellung
n=∏p∣npkpn = \prod\limits_{p\mid n} p^{k_p} (pp ist Primzahl),
so gilt
φ(n)=∏p∣npkp−1(p−1)=n∏p∣n(1−1p)\varphi(n) = \prod\limits_{p\mid n} p^{k_p-1}(p-1) = n \prod\limits_{p\mid n}(1-\dfrac{1}{p})
Beispiel
φ(72)=φ(23⋅32)\phi(72) = \phi(2^{3}·3^{2}) = 23−1⋅(2−1)⋅32−1⋅(3−1)2^{3-1}·(2-1) · 3^{2-1}·(3-1) =22⋅1⋅3⋅2=24= 2^{2} · 1 · 3 · 2 = 24

Abschätzung

Eine Abschätzung für das arithmetische Mittel von φ(n)\phi(n) erhält man über die Formel
∑n=1Nφ(n)=12ζ(2)N2+O(Nlog⁡N)\sum\limits_{n=1}^N \varphi(n) = \dfrac{1}{2 \zeta(2)} N^2 + \O(N \log N),
wobei ζ\zeta die Riemannsche Zetafunktion und O\O das Landau-Symbol ist.
Das heißt: Im Mittel ist φ(n)n≈π212\dfrac{\varphi(n)}{n} \approx \dfrac{\pi^2}{12}.
 
 

Manche Menschen haben einen Gesichtskreis vom Radius Null und nennen ihn ihren Standpunkt.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Eulersche Phi-Funktion aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Zahlentheorie