Eulersche Phi-Funktion

Die eulersche Phi-Funktion ist eine zahlentheoretische Funktion. Sie ordnet jeder natürlichen Zahl \(\displaystyle n\) die Anzahl der natürlichen Zahlen \(\displaystyle a\) von 1 bis \(\displaystyle n\) zu, die zu \(\displaystyle n\) teilerfremd sind, für die also \(\displaystyle \ggT(a,n) = 1\) ist.

Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben \(\displaystyle \phi\) (Phi) bezeichnet.

Beispiele

  • Die Zahl 6 ist zu zwei Zahlen zwischen 1 und 6 teilerfremd (1 und 5), also ist \(\displaystyle \phi\)(6) = 2.
  • Die Zahl 13 ist als Primzahl zu den zwölf Zahlen von 1 bis 12 teilerfremd, also ist \(\displaystyle \phi\)(13) = 12.
  • Die ersten 20 Werte der \(\displaystyle \phi\)-Funktion lauten:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
\(\displaystyle 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 \(\displaystyle p\) nur durch 1 und sich selbst teilbar sind, sind sie sicher zu den Zahlen 1 bis \(\displaystyle p\)-1 teilerfremd, daher ist \(\displaystyle \phi\)(\(\displaystyle p\)) = \(\displaystyle p\)-1.

Potenz von Primzahlen

Eine Potenz \(\displaystyle p^{k}\) aus einer Primzahl \(\displaystyle p\) und einer natürlichen Zahl \(\displaystyle k\) ist nur zu Vielfachen von \(\displaystyle p\) nicht teilerfremd. Es gibt \(\displaystyle p^{k-1}\) Vielfache von \(\displaystyle p\), die kleiner oder gleich \(\displaystyle p^{k}\) sind (1*\(\displaystyle p\), 2*\(\displaystyle p\), ..., \(\displaystyle p^{k-1}\)*\(\displaystyle p\)). Daher gilt:

\(\displaystyle \varphi(p^k) = p^k-p^{k-1} \) \(\displaystyle = p^{k-1}(p-1)= p^{k}(1-1/p)\)

Beispiel

\(\displaystyle \phi\)(16) = \(\displaystyle \phi(2^{4})\) = \(\displaystyle 2^{4} - 2^{3}\) = \(\displaystyle 2^{3} * (2 - 1)\) = \(\displaystyle 2^{4}\) * (1-1/2) = 8 * 1 = 8

Multiplikativität

Die \(\displaystyle \phi\)-Funktion ist multiplikativ für teilerfremde natürliche Zahlen:

\(\displaystyle \varphi(mn) = \varphi(m)\varphi(n)\), falls \(\displaystyle \ggT(m, n) = 1\)

Beispiel:

\(\displaystyle \phi\)(18) = \(\displaystyle \phi\)(2)*\(\displaystyle \phi\)(9) = 1*6 = 6

Gegenbeispiel für Zahlen \(\displaystyle m\) und \(\displaystyle n\) mit gemeinsamem Primfaktor:

\(\displaystyle \phi\)(2*4) = \(\displaystyle \phi\)(8) = 4, aber \(\displaystyle \phi\)(2)*\(\displaystyle \phi\)(4) = 1*2 = 2.

Zusammengesetzte Zahlen

Die Berechnung von \(\displaystyle \phi\)(\(\displaystyle n\)) für zusammengesetzte Zahlen \(\displaystyle n\) ergibt sich aus der Multiplikativität. Hat \(\displaystyle n\) die kanonische Darstellung

\(\displaystyle n = \prod\limits_{p\mid n} p^{k_p}\) (\(\displaystyle p\) ist Primzahl),

so gilt

\(\displaystyle \varphi(n) = \prod\limits_{p\mid n} p^{k_p-1}(p-1) = n \prod\limits_{p\mid n}(1-\dfrac{1}{p})\)

Beispiel

\(\displaystyle \phi(72) = \phi(2^{3}·3^{2})\) = \(\displaystyle 2^{3-1}·(2-1) · 3^{2-1}·(3-1)\) \(\displaystyle = 2^{2} · 1 · 3 · 2 = 24\)

Abschätzung

Eine Abschätzung für das arithmetische Mittel von \(\displaystyle \phi(n)\) erhält man über die Formel

\(\displaystyle \sum\limits_{n=1}^N \varphi(n) = \dfrac{1}{2 \zeta(2)} N^2 + \O(N \log N)\),

wobei \(\displaystyle \zeta\) die Riemannsche Zetafunktion und \(\displaystyle \O\) das Landau-Symbol ist.

Das heißt: Im Mittel ist \(\displaystyle \dfrac{\varphi(n)}{n} \approx \dfrac{\pi^2}{12}\).

Nicht etwa, daß bei größerer Verbreitung des Einblickes in die Methode der Mathematik notwendigerweise viel mehr Kluges gesagt würde als heute, aber es würde sicher viel weniger Unkluges gesagt.

Karl Menger

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е

 

Zahlentheorie