Piccolo teorema di Fermat

Il piccolo teorema di Fermat dice che se $p$ è un numero primo, allora per ogni intero $a$:

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

Questo significa che se si prende un qualunque numero $a$, lo si moltiplica per se stesso $p$ volte e si sottrae $a$, il risultato è divisibile per $p$ (vedi aritmetica modulare). È spesso espresso nella forma equivalente: se $p$ è primo e $a$ è un intero coprimo con $p$, allora:

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

Va notato che la prima espressione è in un certo senso più generale: è infatti valida per numeri interi $a$ arbitrari, come $0$ o multipli di $p$, che invece non rientrano nelle ipotesi della seconda.

È chiamato il piccolo teorema di Fermat per differenziarlo dall'ultimo teorema di Fermat.

Il piccolo teorema di Fermat è la base del test di primalità di Fermat.

Storia

Pierre de Fermat enunciò il teorema attorno al 1636Template:Senza fonte. Compare in una delle sue lettere, datata 18 ottobre 1640 al suo confidente Frenicle nella forma: $p$ divide $a^{p-1}-1$ se $p$ è primo ed $a$ e $p$ sono coprimi.

I matematici cinesi fecero indipendentemente l'ipotesi collegata (talvolta chiamata ipotesi cinese) secondo cui $p$ è primo se e solo se $2^p\equiv 2(\mathrm{mod}p)$. È vero che se $p$ è primo, allora $2^p\equiv 2(\mathrm{mod}p)$ (è un caso particolare del piccolo teorema di Fermat), ma l'inverso (se $2^p\equiv 2(\mathrm{mod}p)$ allora $p$ è primo), e quindi l'ipotesi in generale, è falso (ad esempio $341=11\cdot 31$ è uno pseudoprimo, vedi sotto).

È largamente riconosciuto che l'ipotesi cinese fu sviluppata circa 2000 anni prima del lavoro di Fermat nel 1600. Per quanto l'ipotesi sia parzialmente sbagliata, è degno di nota il fatto che era nota ai matematici antichi. Alcuni, tuttavia, sostengono che l'ampiamente diffusa convinzione che l'ipotesi fosse diffusa da così tanto tempo sia nata da un'incomprensione, e che in realtà fu sviluppata nel 1872.

Dimostrazioni

Template:Vedi anche Fermat espose il suo teorema senza una dimostrazione. Il primo che lo dimostrò fu Gottfried Wilhelm Leibniz in un manoscritto non datato, dove scrisse anche che conosceva una dimostrazione da prima del 1683.

Generalizzazioni

Una piccola generalizzazione del teorema, che deriva immediatamente da questo, è la seguente: se $p$ è primo e $m$ e $n$ sono interi positivi con $m\equiv n(\mathrm{mod}p-1)$, allora $a^m\equiv a^n(\mathrm{mod}p)$ per ogni intero $a$. In questa forma, il teorema giustifica il sistema di cifratura a chiave pubblica RSA.

Il piccolo teorema di Fermat è generalizzato dal teorema di Eulero: per ogni modulo $n$ ed ogni intero $a$ coprimo rispetto a $n$, si ha:

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

Dove $\phi (n)$ indica la funzione phi di Eulero, che conta il numero di interi fra $1$ ed $n$ coprimi rispetto a $n$. Si tratta di una generalizzazione in quanto se $n=p$ è un numero primo, allora $\phi (p)=p-1$.

Questo può essere ulteriormente generalizzato con la funzione di Carmichael.

Il teorema ha anche una bella generalizzazione nei campi finiti.

Pseudoprimi

Se $a$ e $p$ sono numeri coprimi tali che $a^{p-1}-1$ è divisibile per $p$, non è necessario che $p$ sia un numero primo. Se non lo è, allora $p$ è chiamato pseudoprimo rispetto alla base $a$. Nel 1820 F. Sarrus scoprì che $341=11\cdot 31$ è uno dei primi pseudoprimi rispetto alla base $2$.

Un numero $p$ che è pseudoprimo rispetto alla base $a$ per ogni $a$ coprimo rispetto a $p$ è chiamato numero di Carmichael. Un esempio di numero di Carmichael è $561$.

Bibliografia

• H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 88-08-09154-6 - Capitolo II.3

Voci correlate

• Teorema di Eulero (aritmetica modulare)
• RSA
• Aritmetica modulare
• Endomorfismo di Frobenius

Collegamenti esterni

• Template:Collegamenti esterni
• Template:Cita web
• Template:Cita web