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:
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 rispetto a p, allora:
È 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.
Indice |
[modifica] Storia
Pierre de Fermat scoprì il teorema attorno al 1636. Compare in una delle sue lettere, datata 18 ottobre 1640 al suo confidente Frenicle nella forma: p divide ap−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 2p = 2(mod p). È vero che se p è primo, allora 2p = 2(mod p) (è un caso particolare del piccolo teorema di Fermat), ma l'inverso (se 2p = 2(mod p) allora p è primo), e quindi l'ipotesi in generale, è falso (ad esempio 341=11×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.
[modifica] Dimostrazioni
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.
[modifica] 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 ≡ n (mod p − 1), allora am ≡ an (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:
Dove φ(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 φ(p) = p − 1.
Questo può essere ulteriormente generalizzato con il teorema di Carmichael.
Il teorema ha anche una bella generalizzazione nei campi finiti.
[modifica] Pseudoprimi
Se a e p sono numeri coprimi tali che ap−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×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.
[modifica] Bibliografia
- H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo II.3
[modifica] Collegamenti esterni
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
