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 \(n\) die Anzahl der natürlichen Zahlen \(a\) von 1 bis \(n\) zu, die zu \(n\) teilerfremd sind, für die also \(\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)\) 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 \(p\) nur durch 1 und sich selbst teilbar sind, sind sie sicher zu den Zahlen 1 bis \(p\)-1 teilerfremd, daher ist \(\phi\)(\(p\)) = \(p\)-1.

Potenz von Primzahlen

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

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

Beispiel

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

Multiplikativität

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

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

Beispiel:

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

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

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

Zusammengesetzte Zahlen

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

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

so gilt

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

Beispiel

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

Abschätzung

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

\(\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\) das Landau-Symbol ist.

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

Die Logik ist die Hygiene, deren sich der Mathematiker bedient, um seine Gedanken gesund und kräftig zu erhalten.

Hermann Weyl

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: 26.01.2015 18:02:03 (468 ms; 270 M)
C: 29.01.2015 17:15:44 (29 ms; 390 M)