Dimostrazioni del piccolo teorema di Fermat

Qui di seguito troverete una collezione di dimostrazioni del Piccolo teorema di Fermat:

$a^p\equiv a$ (mod $p$)

per ogni numero primo $p$ ed ogni intero $a$.

Semplificazione

È da notare che basta provare

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

per ogni intero $a$ primo con $p$. Moltiplicando ambo i membri dell'ultima espressione per $a$ si ottiene la versione esposta a inizio pagina del teorema. Se $a$ non fosse primo con $p$ allora $a^p\equiv 0\equiv a(\mathrm{mod}p)$ ed il teorema risulterebbe vero in ogni caso.

Dimostrazione sfruttando i multipli del numero intero

Sfruttando la semplificazione proposta nel precedente paragrafo, si considerino i multipli di $a$ che vanno da $a$ stesso fino a $(p-1)a$. Nessuno di questi multipli può dare resto $0$ diviso per $p$ perché né $p-1$ né $a$ sono multipli interi di $p$. Inoltre non può esistere una coppia di questi multipli che sia congrua modulo $p$, perché, se fosse per esempio

$ra\equiv sa(\mathrm{mod}p)$

si avrebbe

$(r-s)a\equiv 0(\mathrm{mod}p)$

Ma questo è impossibile, perché allora $p$ dovrebbe dividere uno dei due fattori. Ma $a$ è primo con $p$, e $r-s$, essendo $r$ ed $s$ numeri naturali compresi tra $1$ e $p$, è $(r-s)<p$. Per cui i multipli considerati hanno un resto nella divisione per $p$ differente per ciascuno di essi, e differente da $0$. Siccome consideriamo $p-1$ multipli, tali multipli devono essere necessariamente congrui (modulo $p$) ai numeri $1,2,3,\dots ,p-1$ in un certo ordine. Ne segue, per il prodotto di tutti questi multipli:

$a(2a)(3a)...(p-1)a=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)a^{p-1}\equiv 1\cdot 2\cdot 3\cdot \dots \cdot (p-1)(\mathrm{mod}p)$

da cui, ponendo $K=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)$, si ha

$K(a^{p-1}-1)\equiv 0(\mathrm{mod}p).$

Dato che $p$ è primo, l'unico modo affinché ciò avvenga è che o K o il secondo fattore sia divisibile per $p$. (con $p$ primo le classi di modulo n costituiscono un dominio di integrità).

Ma $K$ non è divisibile per $p$, perché non lo è nessuno dei suoi fattori; quindi deve essere

$a^{p-1}-1\equiv 0(\mathrm{mod}p).$

Dimostrazione sfruttando il Teorema di Eulero

Questo teorema può essere visto come un corollario del Teorema di Eulero. Osserviamo che $\varphi (p)=p-1$ per ogni $p$ primo (dove $\varphi$ indica la Funzione φ di Eulero). Per il Teorema di Eulero abbiamo che $a^{\varphi (p)}\equiv 1$ (mod $p$) per ogni $a$. Si ha quindi la tesi.

Dimostrazione come corollario del teorema di Lagrange sui gruppi

Template:Vedi anche L'insieme dei numeri interi positivi minori di $p$ costituisce un gruppo (che chiameremo $G$) rispetto alla moltiplicazione modulo $p$, avente come elemento identità il numero $1$. L'ordine (ossia il numero di elementi) di questo gruppo, che indichiamo come $o(G)$, è esattamente $p-1$. Se $a\in G$, si definisce ordine di $a$ il più piccolo intero positivo $m$ tale che $a^m$ sia l'identità. Un'immediata conseguenza del teorema di Lagrange sui gruppi afferma che $o(a)$ divide $o(G)$. Da questo segue che $a^{o(G)}$ dà necessariamente l'elemento identità del gruppo, essendo $a^{o(G)}=a^{k(o(a))}$. Nel caso specifico, quindi, risulterà $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Dimostrazione per induzione

Dimostriamo il teorema con $a\ge 1$ per induzione su $a$: per $a=1$ allora $1=1^p\equiv 1$. Sia vera la tesi per $a$, cioè $a^p\equiv a$ (mod $p$). Vogliamo mostrare che essa è vera per $a+1$. Per il teorema binomiale, abbiamo che

$(a+1{)}^p=\sum _{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})a^i.$

I coefficienti binomiali $(\genfrac{}{}{0ex}{}{p}{i})=\frac{p!}{i!(p-i)!}$ sono tutti numeri interi e quindi, dato che possono essere riscritti come $\frac{p}{i}(\genfrac{}{}{0ex}{}{p-1}{i-1})$ per $0<i<p$, si ha che $p(\genfrac{}{}{0ex}{}{p-1}{i-1})$ è divisibile per $i$ ($0<i<p$); in particolare (dal momento che $p$ è un numero primo e quindi $i$ non divide $p$) pure il fattore binomiale residuo $(\genfrac{}{}{0ex}{}{p-1}{i-1})$, anch'esso intero, è multiplo di $i$ ($0<i<p$); pertanto $\frac{(\genfrac{}{}{0ex}{}{p-1}{i-1})}{i}$ è pure un numero intero; ne segue che i coefficienti binomiali $(\genfrac{}{}{0ex}{}{p}{i})$ sono (per $0<i<p$) divisibili per $p$ (essendo, come appena dimostrato, $\frac{(\genfrac{}{}{0ex}{}{p}{i})}{p}=\frac{(\genfrac{}{}{0ex}{}{p-1}{i-1})}{i}$ un numero intero) ossia:

$(\genfrac{}{}{0ex}{}{p}{i})\equiv 0(\mathrm{mod}p),0<i<p.$

Otteniamo quindi che

$(a+1{)}^p=\sum _{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})a^i\equiv a^p+1\equiv a+1(\mathrm{mod}p),$

dove la prima equivalenza ($\equiv$) si ottiene eliminando dai $p+1$ addendi della sommatoria tutti quelli (dal secondo al penultimo) per cui $0<i<p$ (essendo tutti, come abbiamo dimostrato, divisibili per $p$) e la seconda (ultima) equivalenza è data dall'ipotesi di induzione. Si ha la tesi.

Se $a$ fosse negativo, allora $-a$ è positivo e per quanto detto sopra

$(-a{)}^p\equiv -a(\mathrm{mod}p),$

ma $(-a{)}^p=(-1{)}^p{a}^p$. Se $p$ è dispari allora $(-1{)}^p=-1$ e quindi otteniamo $-a^p\equiv -a(\mathrm{mod}p)$ che implica la tesi (moltiplicando per $-1$ entrambi i membri), altrimenti l'unico primo pari è $p=2$ ma in tal caso $-1\equiv 1(\mathrm{mod}2)$ e quindi

$(-a{)}^2=a^2\equiv -a\equiv a(\mathrm{mod}2).$