Supponiamo sia vera la prima formulazione, cioè che a^p-1 º 1  (mod p) e consideriamo le due possibilità: o p non divide a, o p divide a.

Nel primo caso,  possiamo moltiplicare entrambi i membri dell’uguaglianza per a e avremo immediatamente che a^p-1×a º 1×a  (mod p) da cui segue la seconda affermazione:   a^p º a  (mod p).

Nel secondo caso, sappiamo che

a º 0  (mod p)  e  a^p º 0  (mod p),

da cui, per la transitività delle congruenze, avremo che a^p º a  (mod p).

Viceversa, supponiamo vera la seconda formulazione del teorema: ora poiché a e p sono relativamente primi fra loro, possiamo semplificare per a la congruenza:

a×a^p-1 º a×1  (mod p)

e ottenere

a^p-1 º 1  (mod p).

Ora se verifichiamo il teorema per la prima formulazione, questa implicherà anche la veridicità della seconda formulazione, poiché abbiamo dimostrato che le due affermazioni sono equivalenti.

Prendiamo un intero k non divisibile per p, allora p non dividerà neanche ak e quindi, per il lemma di divisione, esisterà un unico intero r con 0<r<p tale che ak º r (mod p).

Definiamo la funzione

y_a : {1,2, … , p-1} ¾® {1,2, … , p-1} 

tale che   y_a(k) = r ,

ove r è l’unico intero tale che ak º r (mod p).

La funzione y_a è iniettiva, infatti presi due elementi k e l di {1,2,…,p-1}, abbiamo che

y_a(k) = y_a(l)  se e solo se ak º al  (mod p),

e, poiché MCD(a,p)=1, avremo che questo è vero se e solo se k º l  (mod p) e quindi se solo se k = l, perché entrambi compresi fra 1 e p-1.

Inoltre, poiché y_a è iniettiva in se stessa, la sua iniettività implica anche la suriettività.

Ora abbiamo che

a^p-1× (p-1)! = a^p-1× 1×2× ... × (p-1) = (a×1)(a×2)... (a×(p-1)) = y_a(1) ×y_a(2) ×…×y_a(p-1)=(p-1)!

in particolare l’ultima uguaglianza segue dal fatto che gli interi y_a(1) ×y_a(2) ×…×y_a(p-1) sono gli interi 1,2,…,p-1 in ordine inverso.

Adesso, poiché MCD((p-1)!,p) = 1, possiamo semplificare l’uguaglianza sopra per (p-1)!, da cui avremo l’equazione cercata   a^p-1 º 1  (mod p).