Piccolo teorema di Fermat

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

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

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

${\displaystyle 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 ${\displaystyle 0}$ o multipli di ${\displaystyle 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 1636^{[senza fonte]}. Compare in una delle sue lettere, datata 18 ottobre 1640 al suo confidente Frenicle nella forma: ${\displaystyle p}$ divide ${\displaystyle a^{p-1}-1}$ se ${\displaystyle p}$ è primo ed ${\displaystyle a}$ e ${\displaystyle p}$ sono coprimi.

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

Lo stesso argomento in dettaglio: Dimostrazioni del piccolo teorema di Fermat.

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 ${\displaystyle p}$ è primo e ${\displaystyle m}$ e ${\displaystyle n}$ sono interi positivi con ${\displaystyle m\equiv n{\pmod {p-1}}}$, allora ${\displaystyle a^{m}\equiv a^{n}{\pmod {p}}}$ per ogni intero ${\displaystyle 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 ${\displaystyle n}$ ed ogni intero ${\displaystyle a}$ coprimo rispetto a ${\displaystyle n}$, si ha:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

Dove ${\displaystyle \varphi (n)}$ indica la funzione phi di Eulero, che conta il numero di interi fra ${\displaystyle 1}$ ed ${\displaystyle n}$ coprimi rispetto a ${\displaystyle n}$. Si tratta di una generalizzazione in quanto se ${\displaystyle n=p}$ è un numero primo, allora ${\displaystyle \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

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

Un numero ${\displaystyle p}$ che è pseudoprimo rispetto alla base ${\displaystyle a}$ per ogni ${\displaystyle a}$ coprimo rispetto a ${\displaystyle p}$ è chiamato numero di Carmichael. Un esempio di numero di Carmichael è ${\displaystyle 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

Altri progetti

• Wikimedia Commons contiene immagini o altri file sul Piccolo teorema di Fermat

Collegamenti esterni

• (EN) William L. Hosch, Fermat’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Piccolo teorema di Fermat, su MathWorld, Wolfram Research.
• (EN) Il piccolo teorema di Fermat, su cut-the-knot.org. URL consultato il 15 dicembre 2022 (archiviato dall'url originale il 31 gennaio 2012).
• (EN) La funzione di Eulero e il teorema ^{[collegamento interrotto]}, su cut-the-knot.org.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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