Phi-Funktion

Die ersten tausend Werte von $\varphi(n)$

Die eulersche $\varphi$-Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen $a \le n$ zu ihr teilerfremd sind:

$\varphi(n) \; := \; \Big| \{ 1 \le a \le n \, |\, \operatorname{ggT}(a,n) = 1 \} \Big|$

Dabei bezeichnet $\operatorname{ggT}(a,n)$ den größten gemeinsamen Teiler von a und n.

Die $\varphi$-Funktion ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben $\varphi$ (phi) bezeichnet.

Beispiele

• Die Zahl 6 ist zu zwei der Zahlen von 1 bis 6 teilerfremd (1 und 5), also ist $\varphi(6) = 2$.
• Die Zahl 13 ist als Primzahl zu den zwölf Zahlen 1 bis 12 teilerfremd, also ist $\varphi$(13) = 12.
• Die ersten zehn Werte der $\varphi$-Funktion lauten:

n	1	2	3	4	5	6	7	8	9	10
teilerfremde Reste	1	1	1, 2	1, 3	1, 2, 3, 4	1, 5	1, 2, 3, 4, 5, 6	1, 3, 5, 7	1, 2, 4, 5, 7, 8	1, 3, 7, 9
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4

Eigenschaften

Multiplikative Funktion

Die $\varphi$-Funktion ist eine multiplikative zahlentheoretische Funktion. Das heißt, dass für teilerfremde Zahlen m und n die Gleichung

$\varphi (m \cdot n) = \varphi (m) \cdot \varphi (n)$

gilt. Beispielsweise ist

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

Dichte

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

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

Was äquivalent zu $ab\equiv 1 \, \mathrm{mod} \, n$ und $ab+nx=1\,$ ist, wenn man $x\in\Bbb{Z}$ geeignet wählt.

Nach dem Lemma von Bézout ist dies ä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.

Berechnung

Primzahlen

Da jede Primzahl p nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis p − 1 teilerfremd. Es gilt daher

$\varphi(p) = p-1$

Potenz von Primzahlen

Eine Potenz p^k mit einer Primzahl p als Basis und einer natürlichen Zahl k als Exponent hat mit p nur einen Primfaktor. Infolgedessen hat p^k nur mit Vielfachen von p einen von eins verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis p^k sind das die Zahlen

$1\cdot p, 2\cdot p, 3\cdot p, \cdots, p^{k-1} \cdot p = p^k$

Das sind p^{k − 1} Zahlen, die nicht teilerfremd zu p^k sind. Für die eulersche $\varphi$-Funktion gilt deshalb die Formel

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

Beispiel:

$\varphi(16)=\varphi(2^4)=2^4-2^3=2^3\cdot (2-1)=2^4\cdot\left(1-\frac12\right)=8$

Allgemeine Berechnungsformel

Der Wert der eulerschen $\varphi$-Funktion lässt sich für jede Zahl aus ihrer kanonischen Primfaktorzerlegung

$n = \prod_{p\mid n} p^{k_p}$

berechnen:

$\varphi(n) = \prod_{p\mid n} p^{k_p-1}(p-1) = n \prod_{p\mid n}\left(1-\frac{1}{p}\right)$

Diese Formel folgt direkt aus der Multiplikativität der $\varphi$-Funktion und der Formel für Primzahlpotenzen.

Beispiel:

$\varphi(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 $\varphi$(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 $\varphi$-Funktion

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

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

$m \mid a^{\varphi(m)}-1$ (m teilt a hoch Phi von m minus 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 unter anderem Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Weblinks

• Die ersten 10000 Werte der $\varphi$-Funktion
• Programme zur $\varphi$-Funktion
• Folge der Funktionswerte $\varphi$(n): Folge A000010 in OEIS