Eulersche Phi-Funktion

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\leq n$ zu ihr teilerfremd sind:

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

$\varphi (n)\;:=\;{\Big |}\{1\leq a\leq 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 ${\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+nx=1\,$ ist, wenn man $x\in {\mathbb {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-{\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$

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 100000 Werte der $\varphi$-Funktion
• Programme zur $\varphi$-Funktion
• Folge der Funktionswerte $\varphi$(n): Folge A000010 in OEIS