Apri il menu principale

Piccolo teorema di Fermat

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

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

Va notato che la prima espressione è in un certo senso più generale: è infatti valida per numeri interi arbitrari, come o multipli di , 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.

StoriaModifica

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:   divide   se   è primo ed   e   sono coprimi.

I matematici cinesi fecero indipendentemente l'ipotesi collegata (talvolta chiamata ipotesi cinese) secondo cui   è primo se e solo se  . È vero che se   è primo, allora   (è un caso particolare del piccolo teorema di Fermat), ma l'inverso (se   allora   è primo), e quindi l'ipotesi in generale, è falso (ad esempio   è 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.

DimostrazioniModifica

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.

GeneralizzazioniModifica

Una piccola generalizzazione del teorema, che deriva immediatamente da questo, è la seguente: se   è primo e   e   sono interi positivi con  , allora   per ogni intero  . 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   ed ogni intero   coprimo rispetto a  , si ha:

 

Dove   indica la funzione phi di Eulero, che conta il numero di interi fra   ed   coprimi rispetto a  . Si tratta di una generalizzazione in quanto se   è un numero primo, allora  .

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

Il teorema ha anche una bella generalizzazione nei campi finiti.

PseudoprimiModifica

Se   e   sono numeri coprimi tali che   è divisibile per  , non è necessario che   sia un numero primo. Se non lo è, allora   è chiamato pseudoprimo rispetto alla base  . Nel 1820 F. Sarrus scoprì che   è uno dei primi pseudoprimi rispetto alla base  .

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

BibliografiaModifica

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

Voci correlateModifica

Altri progettiModifica

Collegamenti esterniModifica

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