În matematică , mica teoremă a lui Fermat este un rezultat al aritmeticii modulare , care poate fi demonstrată și cu instrumentele aritmeticii elementare .
Se citește după cum urmează: „ în cazul în care p este un număr prim și dacă o este un număr întreg care nu este divizibil cu p , atunci o p -1 - 1 este o multiplu de p “, cu alte cuvinte (în aceleași condiții pe o și p ) , un p –1 este congruent cu 1 modul p :
.O afirmație echivalentă este: "dacă p este un număr prim și dacă a este orice număr întreg , atunci un p - a este un multiplu al lui p ":
.Își datorează numele lui Pierre de Fermat , care l-a declarat pentru prima dată în 1640 .
Are multe aplicații, atât în aritmetica modulară , cât și în criptografie .
Prima apariție cunoscută din situația acestei teoreme provine dintr - o scrisoare de la Fermat la Frénicle de Bessy datatăOctombrie 1640, care a fost publicat de fiul său Samuel în 1679 în Opera Varia . Putem citi acest lucru: „Orice număr prim măsoară infailibil una dintre puterile - 1 a oricărei progresii, iar exponentul puterii menționate este un multiplu al numărului prim dat - 1; și, după ce am găsit prima putere care satisface întrebarea, toți cei ai căror exponenți sunt multipli ai exponentului primului încă satisfac întrebarea. » , Adică în termeni moderni, pentru orice număr prim p și orice număr a (prim cu p ), există un număr întreg t astfel încât p împarte a t - 1 și, t fiind cel mai mic număr întreg care îndeplinește acest lucru, t împărțiri p - 1 și toate multiplii n de t verifica dacă p divide o n - 1.
Deducem imediat afirmația dată în introducere și, reciproc, deducem cu ușurință afirmația mai precisă dată de Fermat. Ca de obicei în corespondența sa, Fermat nu oferă nicio dovadă a acestui rezultat, nici măcar, așa cum o face uneori, a indicațiilor despre acesta, ci specifică: „Și această propoziție este, în general, adevărată în toate progresele și în toate numerele. de care vă voi trimite demonstrația, dacă nu mi-e frică să durez prea mult. "
În acest moment, se obișnuia să nu se publice dovezile teoremelor. Astfel, Leibniz a scris o demonstrație în jurul anului 1683, dar nu a publicat-o. În 1741, 1750 și 1761, Euler a publicat două care continuă prin recurență și utilizează dezvoltarea binomului și una care studiază distribuția resturilor modulo numărul prim considerat. O găsim în 1801 în Disquisitiones Arithmeticae of Gauss . De asemenea, el rezumă prima demonstrație a lui Euler și oferă o versiune mai rapidă a acesteia folosind dezvoltarea multinomialului .
Gauss menționează în 1801 că „Această remarcabilă teoremă, atât pentru eleganța sa, cât și pentru marea sa utilitate, se numește de obicei teorema lui Fermat , după numele inventatorului”. Numele teoremei lui Fermat ( kleine Fermatsche Satz ) îl găsim într-o lucrare a lui Kurt Hensel din 1913.
Un tânăr student american , citat printre alții de Dickson, susținuse că teorema era deja cunoscută în China cu 2000 de ani înainte de Fermat, în cazul particular a = 2, însoțit de un reciproc - banal fals. Această „ ipoteză chineză (în) ” este doar o legendă urbană , datorită unei erori de traducere care s-a amplificat și a denaturat peste ghilimele .
Iată câteva exemple (bazate pe a doua afirmație):
Aplicațiile sunt numeroase, în special în criptografie . Există, totuși, exemple clasice de aplicații ale teoremei în matematica pură .
Mică teoremă a lui Fermat este utilizată istoric pentru a analiza descompunerea produsului factorilor primi ai anumitor numere întregi. Astfel Fermat i-a scris lui Mersenne ( 1588 - 1648 ) : „Mă întrebați dacă numărul 100 895 598 169 este prim sau nu, și o metodă pentru a afla, în spațiul unei zile, dacă este prim sau compus . La această întrebare, răspund că acest număr este compus și este format din produsul acestor două: 898 423 și 112 303, care sunt prime. Folosind o metodă analogă, Euler invalidează conjectura falsă unică a lui Fermat, demonstrând că numerele Fermat nu sunt toate prime.
Această teoremă este de asemenea utilizată pentru a demonstra rezultatele teoriei numerelor algebrice , cum ar fi teorema Herbrand-Ribet . Acesta depășește cadrul strict al aritmeticii , cu o utilizare pentru studierea punctelor fixe ale endomorfismului lui Frobenius, de exemplu.
Criptografia cu cheie publică este un cod care urmărește să asigure confidențialitatea mesajelor folosind două chei de criptare . Unul, care permite criptarea mesajului, este public. Celălalt, cu scopul decriptării, este păstrat secret.
O familie importantă de sisteme asimetrice folosește algoritmul de criptare RSA . Cheia secretă este descompunerea unui număr întreg mare, adesea de câteva sute de cifre. Conține doi factori primi . Cele mai multe dintre tehnicile industriale de la începutul XXI - lea secol sa bazat pe mica Fermat teorema pentru a genera numere prime mari sau pentru a testa primality unui număr.
Micuța teoremă a lui Fermat oferă o condiție necesară pentru ca un număr p să fie prim. Într - adevăr, pentru orice o mai mică decât p , un p - 1 trebuie să fie congruente cu 1 modulo p . Acest principiu stă la baza testului de primărie Fermat . Există multe variații algoritmice ale acestui test. Cele mai cunoscute sunt testul de primărie Solovay-Strassen și mai ales testul de primărie Miller-Rabin .
Testele anterioare utilizează o condiție necesară, dar nu suficientă. Astfel, există numere întregi non-prime p astfel încât pentru toate un prim cu p , un p - 1 este întotdeauna congruent cu 1 modul p . Numărul 1.729 este un exemplu. Astfel de numere întregi p se numesc numere Carmichael .
Testele indicate în paragraful anterior sunt toate statistice, în sensul că există întotdeauna o probabilitate, uneori foarte scăzută, că numărul care a trecut testul nu este totuși primul. Aceste numere se numesc pseudoprime și sunt legate de anumite teste.
A doua dovadă a lui Euler a primei afirmații, preluată de Gauss, reformulată în termeni moderni, constă în a arăta că ordinea t a a din grupul multiplicativ (ℤ / p ℤ) * este un divizor al ordinului p - 1 al acestei grup (demonstrează, prin urmare , teorema Lagrange în cazul particular al subgrupului generat de a ). El deduce imediat mica teoremă a lui Fermat, ridicând cei doi membri ai ecuației a t ≡ 1 (mod p ) la putere: numărul întreg ( p - 1) / t . Rezultatul și dovada acestuia sunt valabile pentru orice grup finit (aici grupul multiplicativ (ℤ / p ℤ) * de ordinul p - 1).
Dovada lui Euler și Leibniz a celei de-a doua afirmații folosește formula binomială a Newton și raționamentul prin inducție asupra întregului a , presupus a fi pozitiv fără pierderea generalității . Raționamentul lor (reformulat aici în limbajul congruențelor introdus ulterior de Gauss), este după cum urmează:
Dacă prima afirmație este adevărată, atunci și a doua: a p - a este egal cu produsul a ( a p –1 - 1) prin urmare este întotdeauna divizibil cu p , deoarece dacă primul factor, a , nu este, atunci al doilea este.
Dimpotrivă, prima afirmație este dedusă din a doua folosind lema lui Euclid : dacă a ( a p –1 - 1) este divizibil cu p și dacă a nu, atunci un p –1 - 1 este.
O altă dovadă a primei afirmații este analogă (în termeni mai simpli) cu o dovadă a lemei lui Gauss : trucul de aici este evaluarea modulului p , în două moduri, produsul
.Dovada este foarte rapidă efectuând calcule în inelul ℤ / p ℤ , dar o putem detalia și folosind doar diviziunea euclidiană , lema lui Euclid și o proprietate algebrică de congruență asupra numerelor întregi .
DemonstrațieSă presupunem că a nu este divizibil cu p și notăm
N produsul a .2 a .3 a . .... ( P - 1) a r k restul diviziunii euclidiene a ka cu p , pentru orice număr întreg k de la 1 la p - 1. ApoiTeorema lui Fermat Mica poate fi demonstrată prin numărarea în două moduri diferite , numărul de P- simbol cuvinte într - un a- simbol alfabet cu cel puțin două simboluri diferite.
O ușoară generalizare a teoremei este următoarea: dacă p este un număr prim și dacă m și n sunt numere întregi strict pozitive astfel încât m ≡ n mod ( p - 1) atunci, pentru orice număr întreg a :
.Într-adevăr, modul p , cei doi membri sunt congruenți la 0 dacă a este divizibil cu p , iar dacă nu este, atunci a n - m = ( a p - 1 ) ( n - m ) / ( p - 1) ≡ 1 ( n - m ) / ( p - 1) = 1. În această formă, teorema întemeiază algoritmul de criptare RSA .
Teorema mică a lui Fermat este generalizată de teorema lui Euler : pentru orice număr natural n -nul și orice număr întreg un prim cu n , avem
unde denotă indicatorul Euler al lui n , egal cu ordinea grupului de unități ale inelului ℤ / n ℤ . Dacă n este un număr prim, atunci φ ( n ) = n - 1 și găsim mica teoremă a lui Fermat.
Se generalizează în același mod la orice câmp finit și, prin urmare, la orice coeficient al inelului numerelor întregi ale unui câmp numeric de un ideal prim .
Cotația Fermat a (în)