Teorema di Eulero

Teorema di Eulero

Considero $\phi$ la funzione di Eulero e siano $a,n$ due numeri interi.
Risulta che $a^{\phi (n)}\equiv 1\text{ mod }n$

Dim

Consideriamo l’insieme degli elementi unitari di ${\mathbb{Z}}_n$, ossia $\mathcal{U}({\mathbb{Z}}_n)=G$.
Dunque $|G|=|\mathcal{U}({\mathbb{Z}}_n)|=\phi (n)$.
Se $a,n$ sono coprimi, allora $[a{]}_n\in G⟹{\left[a^{\phi (n)}\right]}_n=[a{]}_n^{\phi (n)}=[1{]}_n$.