Quiz on Euler’s Phi Function

Die Eulersche Phi-Funktion $\varphi(n)$ gibt für eine natürliche Zahl $n$ die Anzahl der ganzen Zahlen $k$ mit $1 \le k \le n$ an, die zu $n$ teilerfremd sind.

Für jede Primzahl $p$ gilt $\varphi(p) = p – 1$.

Für jede natürliche Zahl $n$ gilt $\varphi(n) = n – 1$.

Die Phi-Funktion ist multiplikativ in dem Sinne, dass für teilerfremde Zahlen $m$ und $n$ gilt: $\varphi(mn) = \varphi(m)\,\varphi(n)$.

Für eine Primzahlpotenz $p^k$ mit Primzahl $p$ und ganzzahligem $k \ge 1$ gilt $\varphi(p^k) = p^{k-1}(p-1)$.

Für jede natürliche Zahl $n$ mit Primfaktorzerlegung $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ gilt $\varphi(n) = n \prod_{i=1}^k \left(1 – \frac{1}{p_i}\right)$.

Der Eulersche Satz behauptet: Für jede natürliche Zahl $n$ und jede ganze Zahl $a$ gilt $a^{\varphi(n)} \equiv 1 \pmod{n}$.