Logo Mathepedia Mathepedia auf Facebook
Wurzelzieher Blog
 

Zahlentheorie


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}\).

Hochtechnologie ist im wesentlichen mathematische Technologie.

Enquete-Kommission der Amerikanischen Akademie der Wissenschaften

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: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 31.01.2015 14:19:25 (510 ms; 243 M)
C: 05.03.2015 12:52:04 (15 ms; 361 M)