Eulersche φ-Funktion

Für diesen Satz fehlt noch ein Beweis!

Für jede positive natürliche Zahl $n$ gibt die Eulersche φ-Funktion $\varphi(n)$ die Anzahl der modulo $n$ primen Restklassen an, das heißt

$\varphi(n) = \#\left\{ 1 \le a \le n : \operatorname{ggT}(a,n) = 1 \right\}$

Formeln

Gilt für $n$ die kanonische Zerlegung $n = \prod_{i=1}^{r} {p_i}^{\alpha_i}$ , so gilt:

$\varphi(n) = n \prod_{i=1}^{r} \left( 1 - \frac{1}{p_i} \right)$

Für teilerfremde Zahlen a und b ist die φ-Funktion multiplikativ, d.h. es gilt:

$\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$

Eine wichtige Aussage mit Hilfe der φ-Funktion wird im Satz von Euler-Fermat gemacht.

Für alle Primzahlen p gilt: $\varphi(p)=p-1$

$\varphi(2)=1$ , $\varphi(4)=2$ , $\varphi(8)=4$ , $\varphi(10)=4$ .

Wikipedia: Eulersche φ-Funktion