Mica Teoremă a lui Fermat

Mica Teoremă a lui Fermat este o teoremă în teoria numerelor care afirmă că [1] :

Dacă este un număr prim și este un întreg nedivizibil cu atunci este divizibil cu $p$ $A$ $p,$ $a^{p-1}-1$ $p.$

În limbajul teoriei congruentelor : congruent cu 1 modulo un prim . Notație formală: $a^{p-1}$ $p$ $a^{p-1}\equiv 1{\pmod {p}}$

De exemplu, dacă atunci și $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

Mica Teoremă a lui Fermat este un caz special al teoremei lui Euler [2] , care, la rândul său, este un caz special al teoremei lui Carmichael și al teoremei lui Lagrange pentru grupuri ciclice finite . Teorema a fost formulată fără demonstrație de Pierre Fermat , prima demonstrație a fost dată de Leonhard Euler și Gottfried Wilhelm Leibniz .

Mica Teoremă a lui Fermat a devenit una dintre principalele teoreme de cercetare nu numai în teoria numerelor întregi, ci și în domenii mai largi [3] [4] .

Istorie

Pierre Fermat a formulat afirmația originală a teoremei într-o scrisoare din 1640 către matematicianul francez Bernard Frenicle [5] :

Fiecare număr prim este echivalent cu [original: măsoară ] o putere minus unu cu orice bază și un exponent egal cu numărul prim dat minus unu... Și această afirmație este în general adevărată pentru toate bazele și toate numerele prime. Ți-aș trimite dovada dacă nu ar fi atât de lungă.

Textul original (fr.)[ arataascunde] Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l'exposant de la dite puissance este sous-multiple du nombre premier donné −1… ; de quoi je vous envoierois la demonstration, si je n'appréhendois d'être trop long. — Sursa: Fermat a Frenicle

Ca exemplu, Fermat dă progresia 3, 9, 27, 81, 243, 729... și numărul prim 13. 13 împarte 27 − 1 (exponentul lui 27 este 3, iar 3 împarte 13 − 1), ceea ce implică faptul că 13 împarte și 729 − 1 (exponentul pentru 729 este 6 și este un multiplu al lui 3).

Fermat însuși și-a lăsat teorema fără dovezi. Primul matematician care a găsit o demonstrație a fost Gottfried Wilhelm Leibniz, ale cărui manuscrise indică faptul că a cunoscut dovada înainte de 1683. Leibniz nu știa de rezultatul lui Fermat și a descoperit teorema în mod independent [6] . Cu toate acestea, lucrarea lui Leibniz nu a fost publicată, iar dovada a fost publicată de Euler în 1736 în Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio [7] . În 1806, matematicianul scoțian James Ivory a publicat o demonstrație bazată pe faptul că, dacă trece prin sistemul complet de reziduuri modulo , atunci pentru orice produs non-multiplu trece și prin sistemul complet de reziduuri modulo, această idee stă la baza dovezilor moderne. [8] . $X$ $p$ $A,$ $p,$ $topor$ $p;$

Numărul se numește privat al lui Fermat . Matematicianul rus D. A. Grave a sugerat că câtul lui Fermat nu este niciodată divizibil cu Pentru numerele prime care nu depășesc 1000, acest lucru este adevărat, dar în curând a fost descoperit un contraexemplu: căci câtul lui Fermat este divizibil cu 1093 [9] . ${\frac {a^{p-1}-1}{p)}$ $p.$ $p=1093,a=2$

Formulare alternativă

Următoarea formulare se distinge prin absența cerinței ca numărul să nu fie divizibil cu : $A$ $p$

Dacă este un număr prim și este orice număr întreg , atunci este comparabil cu modulo , adică . $p$ $A$ $a^{p}$ $A$ $p$ $a^{p}\equiv a{\pmod {p}}$

De exemplu, dacă , atunci și . $a=7;p=5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

Este ușor de demonstrat că această formulare se reduce la cea originală. Deci, dacă este divizibil cu , atunci și , i.e. . Dacă nu este divizibil cu , atunci expresia este echivalentă cu expresia [2] . $A$ $p$ $a\equiv 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $A$ $p$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Atât formulările primare, cât și cele alternative pot fi utilizate pentru a testa dacă un anumit număr este prim (vezi mai jos ), dar formularea primară este mai robustă în sensul că respinge mai multe numere compuse . Exemplu: Să verificăm dacă este un număr prim. Fie obținută B într-o formulare alternativă , iar aceasta este comparabilă cu 4 mod 6. Adică, numărul 6 nu este respins, simplitatea lui nu este infirmată. Dacă revenim la teorema inițială: , atunci , și aceasta nu este comparabilă cu 1 mod 6, așa cum ar trebui să fie dacă p este un număr prim. Deci, formula de bază este mai eficientă la eliminarea numerelor compuse. $6$ $a=4.$ $4^{6}=4096=682\times 6+4$ $a^{p-1}\equiv 1{\pmod {p)}$ $4^{6-1}=4^{5}=1024=170\times 6+4$

Dovezi

Demonstrarea teoremei propuse de Leibniz

Se consideră un polinom omogen de gradul p cu n variabile:

S(x,y,z,\dots ,w)=(x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\ puncte+w^{p}).

Deschizând parantezele, obținem coeficientul de la monom (unde cel puțin două dintre puteri nu sunt egale cu zero, iar suma tuturor puterilor este egală cu p ) se numește coeficient multinomial și se calculează prin formula $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alpha ,\beta ,\gamma \ldots \nu$

M={\frac {p!}{\alpha !\beta !\gamma !\dots \nu !}}).

Deoarece puterile sunt mai mici decât atât, numitorul coeficientului multinomial nu conține factori care s-ar putea anula, prin urmare toți coeficienții polinomului sunt multipli . Astfel, următoarea identitate este adevărată: $\alpha ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $p.$

(x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\dots +w^{p})=pH(x,y ,z,\puncte ,w),

unde este un polinom cu coeficienți întregi pozitivi. $H(x,y,z,...,w)$

Fie acum în această identitate atunci (aici n este numărul de variabile din expresia polinomială originală), prin urmare, este un multiplu al . Dacă nu este divizibil cu un număr prim, atunci [10] este divizibil cu acesta . $x=y=...=w=1,H(1,1,1,...,1)=N,$ $n^{p}-n=Np$ $n(n^{p-1}-1)$ $p$ $n$ $p,$ $n^{{p-1}}-1$

Dovada prin inducție

Să demonstrăm că pentru orice prim p și întreg nenegativ a , a p − a este divizibil cu p . Demonstrăm prin inducție pe o .

Baza. Pentru a = 0 , a p − a = 0 și este divizibil cu p .

Tranziție. Fie afirmația adevărată pentru a = k . Să demonstrăm pentru a = k + 1 .

a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \alege l}k^{l}-k-1=k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \alege l}

Dar k p − k este divizibil cu p prin ipoteza de inducție. Restul termenilor conțin factorul . Pentru , numărătorul acestei fracții este divizibil cu p , iar numitorul este coprim cu p , prin urmare, este divizibil cu p . Deoarece toți termenii individuali sunt divizibili cu p , întreaga sumă este de asemenea divizibilă cu p . ${p \choose l}={p! \peste l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \alege l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \alege l}$

Pentru a negativ și p impar , teorema este ușor de demonstrat prin înlocuirea b = − a . Pentru negativ a și p = 2 , adevărul teoremei rezultă din a 2 − a = a ( a − 1) [11] .

Dovada folosind teoria grupurilor

Una dintre cele mai simple dovezi ale Micii Teoreme a lui Fermat se bazează pe un corolar al teoremei lui Lagrange din teoria grupurilor , afirmând că ordinea unui element dintr-un grup finit împarte ordinea grupului.

Reamintim că ordinea unui grup finit este numărul elementelor sale, iar ordinea unui element este cel mai mic exponent natural al gradului său egal cu elementul unitar al grupului . $G$ $g\în G$ $e$ $G$

Fie un grup finit de ordine . Deoarece ordinea elementelor se divide , rezultă că . $G$ $n$ $g\în G$ $n$ $g^{n}=e$

Se consideră câmpul de reziduuri modulo . Deducerea unui număr întreg va fi notat cu . Elementele nenule ale câmpului formează un grup în ceea ce privește înmulțirea. $\mathbb {Z} _{p}$ $p$ $A$ $A$ $\mathbb {Z} _{p}$

Ordinea acestui grup este evident . Singurul său element este . Rezultă că pentru fiecare număr care nu este divizibil cu , , dar aceasta înseamnă doar comparație [1] $p-1$ $unu$ $A$ $p$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Demonstrarea folosind aritmetica modulară

Lema. Pentru orice număr prim și un întreg care nu este un multiplu al lui , produsul lui și numerele atunci când sunt împărțite la rest da aceleași numere , eventual scrise într-o ordine diferită. $p$ $k$ $p$ $k$ $1,2,3,\ldots ,p-1$ $p$ $1,2,3,\ldots ,p-1,$

Dovada lemei

Produsul și oricare dintre numere nu este un multiplu al , prin urmare, restul nu poate fi . Toate rămășițele sunt diferite. Să demonstrăm ultima afirmație prin contradicție. Fie la și două produse și dați la împărțirea la resturi identice, atunci diferența este un multiplu al lui , ceea ce este imposibil, deoarece nu este un multiplu al lui . În total, există resturi diferite de zero de la împărțirea cu . $k$ $1,2,3,\ldots ,p-1$ $p$ $0$ $a,b\in \{1,2,3,\ldots ,p-1\}$ $a\neq b$ $ak$ $bk$ $p$ $ak-bk=(ab)k$ $p$ $ab$ $p$ $p-1$ $p$

Întrucât, conform lemei de mai sus, resturile după împărțirea numerelor a , 2 a , 3 a , ..., ( p − 1) a este, până la o permutare a numărului 1, 2, 3, ... , p − 1 , atunci . De aici . Ultima relație poate fi redusă la ( p − 1)! , întrucât toți factorii sunt numere coprime cu baza p , ca rezultat obținem afirmația necesară [12] . $a\cdot 2a\cdot 3a\ldots (p-1)a\equiv 1\cdot 2\cdot 3\ldots (p-1){\pmod {p))$ $a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p))$ $a^{p-1}\equiv 1{\pmod {p}}$

Consecințe și generalizări

Dacă este un număr prim, atunci egalitatea [13] este adevărată în câmpul . $p$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Dacă este un număr prim, altul decât 2 și 5, atunci numărul a cărui notație zecimală conține doar cifre este divizibil cu . Rezultă că pentru orice număr întreg care nu este divizibil nici cu 2, nici cu 5, puteți ridica un număr format doar din nouă, care este divizibil cu . Acest fapt este folosit în teoria semnelor de divizibilitate și a fracțiilor periodice [14] . $p$ $10^{p-1}-1$ $9$ $p$ $N$ $N$
Mica Teoremă a lui Fermat vă permite să găsiți divizori primi ai numerelor de forma și [15] . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
O generalizare a micii teoreme a lui Fermat la numere algebrice este o teoremă formulată de Schönemann în 1839: fie rădăcinile unui polinom normalizat de gradul d și p un număr prim. Apoi [16] . $a_{1},\dots ,a_{d}$ $f\in \mathbb {Z} [x]$ $a_{1}^{p}+a_{2}^{p}+\dots +a_{d}^{p}\equiv a_{1}+\dots +a_{d}{\pmod {p))$
Mica Teoremă a lui Fermat implică teorema lui Wilson : Un număr natural este prim dacă și numai dacă este divizibil cu p . $p>1$ $(p-1)!+1$

Dovada teoremei lui Wilson

Teorema Lagrange în teoria numerelor afirmă că, dacă un polinom de grad este divizibil cu un număr prim pentru mai multe valori modulo incomparabile (adică, având resturi diferite atunci când este împărțit la ) valori ale variabilei , atunci este divizibil cu la orice valoare . $n$ $p$ $n$ $p$ $p$ $X$ $p$ $X$

Luați în considerare polinomul

G(x)=(x-1)(x-2)(x-3)...(x-(p-1))-(x^{p-1}-1),

unde este un număr prim.

p

Apoi găsim:

G(1)=0,G(2)=1-2^{p-1},G(3)=1-3^{p-1},...,G(p-1)=1- (p-1)^{p-1}.

În virtutea micii teoreme a lui Fermat, toate aceste numere sunt divizibile cu un număr prim , deci comparația are soluții incongruente. Pe de altă parte, gradul unui polinom este doar din aceasta rezultă că polinomul este divizibil cu pentru toate valorile și în special pentru $p$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $p$ $X,$ $x=0.$

Mijloace $G(0)=[(p-1)!+1]\equiv 0{\pmod {p}}.$

Și dacă, pe lângă aceasta, demonstrăm că pentru toate naturii nesimple , cu excepția , , atunci obținem demonstrația teoremei. [17] $n$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Aplicații

Pseudoprime Fermat și testarea primalității

Mica Teoremă a lui Fermat poate fi folosită pentru a testa dacă un număr este prim: dacă nu este divizibil cu , atunci este un număr compus . Cu toate acestea, inversul Micii Teoreme a lui Fermat este în general incorect: dacă și sunt numere coprime și sunt divizibile cu , atunci numărul poate fi atât prim, cât și compus. În cazul în care este compus, se numește pseudosimplu al lui Fermat la bază . $(a^{p}-a)$ $p$ $p$ $A$ $p$ $a^{p-1} - 1$ $p$ $p$ $p$ $A$

De exemplu, ipoteza chineză afirmă că este un număr prim dacă și numai dacă [18] . Iată o afirmație directă că dacă este prim, atunci , este un caz special al teoremei mici a lui Fermat. Afirmația inversă că dacă , atunci este simplă, este un caz special al inversării micii teoreme a lui Fermat. Această conversie este falsă: Sarrus a descoperit în 1820 că un număr este divizibil cu , deoarece este divizibil cu . Cu toate acestea, este un număr compus : . Astfel, este un număr pseudoprim în baza 2 [19] . $p$ $2^{p}\equiv 2{\pmod {p}}$ $p$ $2^{p}\equiv 2{\pmod {p}}$ $2^{p}\equiv 2{\pmod {p}}$ $p$ $N=2^{341-1}-1$ $341$ $N$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

În cazul general, eșuează și inversul Micii Teoreme a lui Fermat. Un contraexemplu în cazul general sunt numerele Carmichael : acestea sunt numere care sunt pseudoprime în bază pentru toate coprime la . Cel mai mic dintre numerele lui Carmichael este 561. $p$ $A$ $A$ $p$

Datorită faptului că inversul micii teoreme a lui Fermat este incorectă, îndeplinirea condiției sale nu garantează că este un număr prim . Cu toate acestea, mica teoremă a lui Fermat stă la baza testului Fermat pentru primalitate [20] . Testul Fermat este un test de primalitate probabilistică: dacă teorema nu este adevărată, atunci numărul este exact compus, iar dacă este, atunci numărul este prim cu o oarecare probabilitate . Printre alte metode probabilistice, se pot observa: testul Solovay-Strassen și testul Miller-Rabin , acesta din urmă se bazează într-o oarecare măsură pe mica teoremă a lui Fermat [21] . Există și un algoritm determinist : testul Agrawal-Kayala-Saksen . $p$

În plus, următoarele două afirmații sunt adevărate. Dacă o pereche satisface comparația , atunci și perechea de numere o satisface. Pentru orice număr prim și orice astfel de care , valoarea este un pseudoprim Fermat la baza [22] . $(2,n)$ $a^{n-1}\equiv 1{\pmod {n}}$ $(2,2^{n}-1)$ $n$ $a>2$ $(a^{2}-1,n)=1$ ${\frac {a^{2n}-1}{a^{2}-1}}$ $A$

Algoritm RSA

Mica Teoremă a lui Fermat este, de asemenea, utilizată pentru a demonstra corectitudinea algoritmului de criptare RSA [2] .

Vezi și

Note

↑ 1 2 Vinberg, 2008 , p. 43.
↑ 1 2 3 Sagalovici, 2014 , p. 34.
↑ Encyclopedia of Elementary Mathematics, Cartea 1, Aritmetica, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961.— P. 280
↑ Z. I. Borevici, I. R. Şafarevici. Teoria numerelor. — M .: Nauka, 1972. — 175 p.
↑ Gracian E. Numere prime. Drum lung spre infinit. - De Agostini, 2014. - T. 3. - S. 45. - 148 p. — (Lumea matematicii). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Numerele - limbajul științei, 2008 , p. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Teoria numerelor prin anchetă Arhivat pe 16 septembrie 2012 la Wayback Machine . - 2006. - pp. 62-63.
↑ John J. O'Connor și Edmund F. Robertson . Sir James Ivory este o biografie din arhiva MacTutor .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. În spatele paginilor unui manual de matematică: Aritmetică. Algebră. Geometrie . - M . : Educaţie, 1996. - S. 30 . — 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Numerele - limbajul științei, 2008 , p. 231-234.
↑ Vinberg, 2008 , p. 44.
↑ QUANTUM, 2000, Nr. 1, Senderov V, Mica teoremă a lui Spivak A. Fermat.
↑ Akritas A. Fundamentals of computer algebra with applications, p. 83.
↑ Danzig, T. Numerele - limbajul științei, 2008 , p. 232-234.
↑ QUANTUM, 2000, nr. 3, Senderov V, Mica teoremă a lui Spivak A Fermat
↑ Vinberg, 2008 , p. 49.
↑ Danzig, T. Numerele sunt limbajul științei, 2008 , p. 234-238.
↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103-105, ISBN 0-387-94457-5 .
↑ Weisstein EW Fermat Pseudoprime .. - 2005 ..
↑ Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Information security: a textbook. - M.: MIPT, 2011. - S. 236-237. — 262 p. Cu. — ISBN 978-5-7417-0377-9 .
↑ Testarea Williams HC Primality pe un computer // Ars Combin. - 1978. - Vol. T. 5 , nr. Nu. 12 . — P. 127-185 .
↑ Shitov Yu. A. Metode numerice în criptografie.

Literatură

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Enciclopedia matematicii elementare. Volumul I: Aritmetica. — 1951.
Borevici Z. I., Shafarevici I. R. Teoria numerelor . — M .: Nauka, 1972. — 510 p. Arhivat pe 8 ianuarie 2011 la Wayback Machine
Vinberg EB Mica Teoremă a lui Fermat și generalizările ei // Matem. iluminarea - M . : Editura MTSNMO , 2008. - T. 12. - S. 43-53.
Gindikin S. G. „Mica teoremă a lui Fermat” . - Kvant , 1972. - Nr. 10 . (link indisponibil)
Danzig, T. Numerele sunt limbajul științei . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Probleme algoritmice ale teoriei numerelor . - 1997. - Emisiune. 2 , nr.a treia serie .
Sagalovici Yu. L. Introducere în codurile algebrice - ed. a 3-a, revizuită. si suplimentare - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Mica Teoremă a lui Fermat // Kvant. - 2000. - Nr. 1 .
Senderov V, Spivak A. Mica Teoremă a lui Fermat // Kvant. - 2000. - Nr. 3 .