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 22 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	21	22
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10

Berechnung

$\varphi (n)\,$ gibt die Anzahl der Einheiten im Restklassenring ${\mathbb {Z} }/n{\mathbb {Z} }$ an.

Denn ist ${\overline {a}}\in {\mathbb {Z} }/n{\mathbb {Z} }$ eine Einheit, also ${\overline {a}}\in ({\mathbb {Z}}/n{\mathbb {Z}})^{*}$, so gibt es ein ${\overline {b}}\in {\mathbb {Z} }/n{\mathbb {Z} }$ mit ${\overline {a}}\cdot {\overline {b}}={\overline {1}}$.

Was äquivalent zu $ab\equiv 1\,\mathrm {mod} \,n$ und $ab+nb'=1\,$ ist, wenn man $b'\in {\mathbb {Z}}$ geeignet wählt.

Nach dem Lemma von Bézout ist diese äquivalent zur Teilerfremdheit von $a\,$ und $n\,$.

$\varphi (n)$ ist für $n>2$ stets eine gerade Zahl.

Ist $a_{n}$ die Anzahl der Elemente aus dem Bild $\mathrm {im} (\varphi )$, die kleinergleich $n$ sind, dann gilt $\lim _{n\to \infty }{\frac {a_{n}}{n}}=0$.

Das Bild der $\varphi$-Funktion besitzt also natürliche Dichte 0.

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 $\varphi (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\cdot p,2\cdot p,...,p^{k-1}\cdot p)$. Daher gilt:

$\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)$

Beispiel:

$\varphi (16)=\varphi (2^{4})=2^{4}-2^{3}=2^{3}\cdot (2-1)=2^{4}\cdot \left(1-{\frac {1}{2}}\right)=8\cdot 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:

$\varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6$

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

$\varphi (2\cdot 4)=\varphi (8)=4$, aber $\varphi (2)\cdot \varphi (4)=1\cdot 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 _{p\mid n}p^{k_{p}}$ (p ist Primzahl),

so gilt

$\varphi (n)=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)$

Beispiel:

$\phi (72)=\varphi (2^{3}\cdot 3^{2})=2^{3-1}\cdot (2-1)\cdot 3^{2-1}\cdot (3-1)=2^{2}\cdot 1\cdot 3\cdot 2=24$

Abschätzung

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

$\sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N)$,

wobei ζ die Riemannsche Zetafunktion und O das Landau-Symbol ist.

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

Bedeutung der $\phi$-Funktion

Eine der wichtigsten Anwendungen findet die $\phi$-Funktion im Satz von Fermat-Euler:

Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind, gilt:

$m\mid a^{\varphi (m)}-1$,

oder anders formuliert:

$a^{\varphi (m)}\equiv 1{\pmod {m}}$

Ein Spezialfall (für Primzahlen p) dieses Satzes ist der Kleine Fermatsche Satz:

$p\mid a^{p-1}-1$,

bzw.

$a^{p-1}\equiv 1{\pmod {p}}$

Der Satz von Fermat-Euler findet u.a. Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Weblinks

• Programme zur $\phi$-Funktion
• Folge der Funktionswerte $\phi$(n): Folge A000010 in OEIS