Dimostrazioni del piccolo teorema di Fermat

Da Wikipedia, l'enciclopedia libera.

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.

[modifica] Semplificazione

È da notare che basta provare

$\, a^{p-1} \equiv 1 \pmod{p}$

per ogni intero a primo con p. Moltiplicando ambo i membri per a si ottiene la versione sopra esposta del teorema. Se a non fosse primo con p allora $a^p\equiv 0\equiv a \pmod{p}$ ed il teorema risulterebbe vero in ogni caso.

[modifica] Dimostrazione sfruttando il Teorema di Eulero

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

[modifica] Dimostrazione per induzione

Dimostriamo il teorema con $a\geq 0$ per induzione su a: per a=0 allora $0=0^p\equiv 0$ . Sia vera la tesi per a, cioe' $\, a^p \equiv a$ (mod p). Vogliamo mostrare che essa e' vera per a+1. Per il Teorema binomiale, abbiamo che

$\, (a+1)^p=\sum_{i=0}^p{p \choose i}a^i,$ .

I coefficienti binomiali ${p \choose i}=\frac{p!}{i!(p-i)!}$ sono tutti numeri interi e, per 0 < i < p, nessun termine al denominatore e' divisibile per p (in effetti ogni denominatore e' prodotto di interi tutti minori di p). Poiché il numeratore e' sicuramente divisibile per p, ne segue che p divide ognuno di tali coefficienti e pertanto

${p \choose i}\equiv 0\pmod{p}, \qquad 0 < i < p$ .

Otteniamo quindi che

$\, (a+1)^p=\sum_{i=0}^p{p \choose i}a^i\equiv a^p + 1\equiv a+1 \pmod{p}$ ,

dove l'ultima equivalenza e' data dall'ipotesi di induzione. Si ha la tesi.

Se a fosse negativo, allora -a e' positivo e per quato detto sopra

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

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