Funzione di Eulero

Funzione di Eulero

La funzione $\phi :\mathbb{N}\to \mathbb{N}$ che associa ad ogni numero $n\in \mathbb{N}$ la quantità di numeri primi minori di $n$
$\phi (n)=\#\{k\in \mathbb{N}|k<n\vee k\text{ eˋ coprimo a }n\}=|\mathcal{U}({\mathbb{Z}}_n)|$
Si dimostra che se $p$ è primo, $\phi (p)=p-1$
Se $k=mn$ con $m,n$ coprimi, allora $\phi (k)=\phi (mn)=\phi (n)\cdot \phi (m)$
$\phi (p^k)=p^k-p^{k-1}$
Questa proprietà è conseguenza del Teorema Cinese del Resto
Ad esempio $\phi (2)=\#\{1\}=1,\phi (3)=\#\{1,2\}=2,\phi (4)=\#\{1,3\}=2$