Piccolo teorema di Fermat
Il piccolo teorema di Fermat dice che se è un numero primo, allora per ogni intero :
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.
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: 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.
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.
Generalizzazioni
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.
Pseudoprimi
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 è .
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
Altri progetti
- Wikimedia Commons
- 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 | ||
---|---|---|
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 |