$\forall m \in \mathbb Z$ sia $\mathbb Z_m^* = \{[a]_m|MCD(a,m)=1\} \subseteq \mathbb Z_m$ l’insieme delle classi di equivalenza di numeri coprimi con $m$
$|\mathbb Z_m^*|$ è detta indicatore di Gauss-Eulero e si indica con $\varphi(m)$
Se $p$ è primo (coprimo con tutti), $\mathbb Z_p^* = \{[1]_p,..,[p-1]_p\}$ quindi $\varphi(p) = p-1$
Per induzione si ha $\varphi(p^n)=p^n-p^{n-1}$
$\begin{cases} \varphi(1) = 1 \\ \varphi(n) = |\{m \in \mathbb N|m < n \space e \space MCD(n,m)=1\}| \end{cases}$ cardinalità dei coprimi $<n$
Lemma: $\forall h,k \in \mathbb N$, $\varphi(hk) = \varphi(h) \cdot \varphi(k)$
Sia $p \in \mathbb N$ primo, allora $\forall a \in \mathbb Z$ $a^p \equiv a \space (mod \space p)$
Se $m>1$ e $a \in \mathbb Z$ è tale che $MCD(a,m)=1$, allora $a^{\varphi(m)} \equiv 1 \space (mod \space m)$
Se $p \in \mathbb N \backslash \{1\}$, allora $p$ è primo $\Leftrightarrow(p-1) \equiv -1 \space (mod \space p)$