\section{Eulersche $\varphi$-Funktion}\label{sec:Eulersche-Phi-Funktion}
Die Eulersche $\varphi$-Funktion gibt für jede natürliche Zahl $n$ an,
wie viele positive ganze Zahlen $a \leq n $ zu ihr relativ prim sind\footnote{[Brill], S. 148}.
$a$ ist zu $n$ relativ prim, wenn $ggT(a,n) = 1$ gilt, also wenn $a$
und $n$ keinen größeren gemeinsamen Teiler als $1$ haben. Man sagt
auch "`a und b sind teilerfremd"'.
$\varphi(n)$ ist zugleich die Ordnung der multiplikativen Gruppe $(\mathbb{Z}/n \mathbb{Z})^*$.
$\varphi(n)$ gibt also an, wie viele Zahlen im Restklassenring modulo $n$ ein multiplikativ Inverses haben. Mehr dazu in \cref{sec:Multiplikativ-Inverses}
Für Primzahlen gilt $\varphi(p) = p - 1$ , da eine Primzahl nur
durch sich und eins teilbar ist. Sei $A$ die multiplikative Gruppe
einer Primzahl $p$, $B$ die multiplikative Gruppe einer Primzahl $q$
und $C$ die multiplikative Gruppe von $p \cdot q$. Dann ist $|C| = |A| \cdot |B|$ und
$\varphi(p \cdot q) = |C|$, $\varphi(p) = |A|$ sowie $\varphi(q) = |B|$.
Daraus folgt, dass $\varphi(pq) = \varphi(p) \cdot \varphi(q) = (p-1) \cdot (q - 1)$ für zwei Primzahlen $p \neq q$ gilt.
