Piccolo teorema di Fermat: differenze tra le versioni

Il '''piccolo [[teorema]] di [[Fermat]]''' dice che se ''<math>p''</math> è un [[numero primo]], allora per ogni [[numero intero|intero]] ''<math>a''</math>:

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

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

[[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: ''<math>p''</math> divide ''a''<supmath>''a^{p''−1-1}-1</supmath> − 1 se ''<math>p''</math> è primo ed ''<math>a''</math> e ''<math>p''</math> sono coprimi.

I matematici cinesi fecero indipendentemente l'ipotesi collegata (talvolta chiamata ''ipotesi cinese'') secondo cui ''<math>p''</math> è primo se e solo se <math>2^p = 2 \pmod{p}</math>. È vero che se ''<math>p''</math> è primo, allora <math>2^p = 2 \pmod{p}</math> (è un caso particolare del piccolo teorema di Fermat), ma l'inverso (se <math>2^p = 2 \pmod{p}</math> allora ''<math>p''</math> è primo), e quindi l'ipotesi in generale, è falso (ad esempio <math>341=11×3111\cdot 31</math> è 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]].

Una piccola generalizzazione del teorema, che deriva immediatamente da questo, è la seguente: se ''<math>p''</math> è primo e ''<math>m''</math> e ''<math>n''</math> sono interi positivi con ''<math>m'' ≡\equiv ''n'' (mod ''\pmod{p'' − -1)}</math>, allora ''a''<supmath>''a^m''</sup> ≡\equiv ''a''^{''^n''} (mod\pmod ''p'')</math> per ogni intero ''<math>a''</math>. In questa forma, il teorema giustifica il sistema di cifratura a [[chiave pubblica]] [[RSA]].

Il piccolo teorema di Fermat è generalizzato dal [[Teorema di Eulero (aritmetica modulare)|teorema di Eulero]]: per ogni modulo ''<math>n''</math> ed ogni intero ''<math>a''</math> [[coprimo]] rispetto a ''<math>n''</math>, si ha:

Dove φ<math>\varphi(''n'')</math> indica la [[funzione phi di Eulero]], che conta il numero di interi fra <math>1</math> ed ''<math>n''</math> coprimi rispetto a ''<math>n''</math>. Si tratta di una generalizzazione in quanto se ''<math>n'' = ''p''</math> è un numero primo, allora φ<math>\varphi(''p'') = ''p'' − -1</math>.

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

Un numero ''<math>p''</math> che è pseudoprimo rispetto alla base <math>a</math> per ogni <math>a</math> coprimo rispetto a ''<math>p''</math> è chiamato [[numero di Carmichael]]. Un esempio di numero di Carmichael è <math>561</math>.