piccolo teorema di Fermat

Teorema

Se $p$ è un numero primo allora

$$a^{\phi (p)}\equiv 1(\mathrm{mod}p)$$

per ogni $a$ che non sia multiplo di $p$.

Osservazione

Se $p$ è un numero primo allora:

i) Possiamo liberarci della condizione ”$a$ non multiplo di $p$” ottenendo

$$a^p\equiv a(\mathrm{mod}p)\forall a\in \mathbb{Z}.$$

Infatti $\phi (p)=p-1$, da cui $a^{\phi (p)}=a^{p-1}\equiv 1(\mathrm{mod}p)$ e moltiplicando entrambi i membri per $a$ si ottiene il risultato sotto le stesse ipotesi del Teorema di Fermat, mentre se $a$ fosse multiplo di $p$ otterremmo la congruenza banale $0\equiv 0(\mathrm{mod}p)$.

ii) Una riformulazione del piccolo teorema di Fermat è la seguente:

In ${\mathbb{Z}}_p$ si ha $[a{]}^p=[a^p]=[a]$.

Dimostrazione

Risorse