Piccolo teorema di Fermat

Da Wikipedia, l'enciclopedia libera.

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

a^p \equiv a \pmod{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 \pmod{p}

Va notato che la prima espressione è in un certo senso più generale: è infatti valida per numeri interi 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[modifica | modifica sorgente]

Pierre de Fermat enunciò il teorema attorno al 1636[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 = 2 \pmod{p}. È vero che se p è primo, allora 2^p = 2 \pmod{p} (è un caso particolare del piccolo teorema di Fermat), ma l'inverso (se 2^p = 2 \pmod{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[modifica | modifica sorgente]

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

Vedi dimostrazioni del piccolo teorema di Fermat.

Generalizzazioni[modifica | modifica sorgente]

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 \pmod{p-1}, allora a^m \equiv a^n \pmod 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^{\varphi (n)} \equiv 1 \pmod{n}

Dove \varphi(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 \varphi(p)=p-1.

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

Il teorema ha anche una bella generalizzazione nei campi finiti.

Pseudoprimi[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica