Fermatin pieni lause

Fermatin pieni lause on lukuteorian lause, joka väittää, että [1] :

If on alkuluku ja on kokonaisluku , joka ei ole jaollinen sitten , on jaollinen $s$ $a$ $p,$ $a^{p-1}-1$ $s.$

Kongruenssiteorian kielellä : kongruentti 1 modulo a alkulukua vastaan . Muodollinen merkintä: $a^{p-1}$ $s$ $a^{p-1}\equiv 1{\pmod {p}}$

Esimerkiksi jos sitten ja $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

Fermatin pieni lause on erikoistapaus Eulerin lauseesta [2] , joka puolestaan on Carmichaelin lauseen ja Lagrangen ryhmälauseen erikoistapaus äärellisille syklisille ryhmille . Lauseen esitti ilman todistetta Pierre Fermat , ensimmäisen todisteen antoivat Leonhard Euler ja Gottfried Wilhelm Leibniz .

Fermatin pienestä lauseesta on tullut yksi tutkimuksen päälauseista ei vain kokonaislukuteoriassa, vaan myös laajemmilla alueilla [3] [4] .

Historia

Pierre Fermat muotoili lauseen alkuperäisen lausuman vuonna 1640 kirjeessään ranskalaiselle matemaatikolle Bernard Freniclelle [5] :

Jokainen alkuluku on yhtä suuri kuin [alkuperäinen: mittaa ] potenssi miinus yksi millä tahansa kantalla ja eksponentti, joka on yhtä suuri kuin annettu alkuluku miinus yksi… Ja tämä väite pätee yleensä kaikille kantaluvuille ja kaikille alkuluvuille. Lähettäisin sinulle todisteen, jos se ei olisi niin pitkä.

Alkuperäinen teksti (fr.)[ näytäpiilottaa] Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné −1… Et cette proposition est généralement vraie en toutes toutes toutes nombre ; de quoi je vous envoierois la demonstration, si je n'appréhendois d'être trop long. — Lähde: Fermat a Frenicle

Esimerkkinä Fermat antaa progression 3, 9, 27, 81, 243, 729… ja alkuluvun 13. 13 jakaa luvun 27 − 1 (luvun 27 eksponentti on 3 ja 3 jakaa luvun 13 − 1), mikä tarkoittaa, että 13 jakaa myös arvon 729 − 1 (729:n eksponentti on 6 ja on 3:n kerrannainen).

Fermat itse jätti lauseensa ilman todisteita. Ensimmäinen matemaatikko, joka löysi todisteen, oli Gottfried Wilhelm Leibniz, jonka käsikirjoitukset osoittavat, että hän tiesi todisteen ennen vuotta 1683. Leibniz ei tiennyt Fermatin tuloksesta ja löysi lauseen itsenäisesti [6] . Leibnizin työtä ei kuitenkaan julkaistu, ja Euler julkaisi todisteen vuonna 1736 teoksessa Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio [7] . Vuonna 1806 skotlantilainen matemaatikko James Ivory julkaisi todisteen, joka perustuu siihen tosiasiaan, että jos se kulkee läpi koko jäännösjärjestelmän modulo , niin minkä tahansa muun kuin usean tuotteen kohdalla myös koko jäännösjärjestelmän modulo tämä ajatus on nykyaikaisten todisteiden perusta. [8] . $x$ $s$ $a,$ $p,$ $kirves$ $p;$

Numeroa kutsutaan Fermatin yksityiseksi . Venäläinen matemaatikko D. A. Grave ehdotti, että Fermatin osamäärä ei ole koskaan jaollinen luvulla 1000:a suuremmille alkuluvuille, mutta pian löydettiin vastaesimerkki: sillä Fermat'n osamäärä on jaollinen luvulla 1093 [9] . ${\frac {a^{p-1}-1}{p))$ $s.$ $p=1093,a=2$

Vaihtoehtoinen sanamuoto

Seuraava muotoilu eroaa siitä, että siinä ei ole vaatimusta, jonka mukaan luku ei ole jaollinen : $a$ $s$

Jos on alkuluku ja mikä tahansa kokonaisluku , niin se on verrattavissa moduloon , eli . $s$ $a$ $a^{p}$ $a$ $s$ $a^{p}\equiv a{\pmod {p}}$

Esimerkiksi jos , sitten ja . $a = 7; p = 5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

On helppo osoittaa, että tämä formulaatio on pelkistetty alkuperäiseen muotoon. Joten, jos on jaollinen , niin ja , ts. . Jos se ei ole jaollinen luvulla , niin lauseke vastaa lauseketta [2] . $a$ $s$ $a\equiv 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $a$ $s$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Sekä ensisijaista että vaihtoehtoista formulaatiota voidaan käyttää testaamaan, onko tietty luku alkuluku (katso alla ), mutta ensisijainen formulaatio on vankempi siinä mielessä, että se hylkää useampia yhdistelmälukuja . Esimerkki: Tarkistetaan, onko se alkuluku. Olkoon B saatu vaihtoehtoisessa formulaatiossa , ja tämä on verrattavissa 4 mod 6:een. Eli lukua 6 ei hylätä, sen yksinkertaisuutta ei kiistetä. Jos palataan alkuperäiseen lauseeseen: , niin , ja tämä ei ole verrattavissa 1 mod 6:n kanssa, kuten sen pitäisi olla jos p on alkuluku. Joten perusformulaatio on tehokkaampi yhdistelmälukujen poistamisessa. $6$ $a=4.$ $4^{6}=4096=682\kertaa 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\kertaa 6+4$

Todisteet

Todistus Leibnizin ehdottamasta lauseesta

Tarkastellaan p - asteista homogeenista polynomia, jossa on n muuttujaa:

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

Hakasulkeet avattaessa saadaan kerroin monomilla (jossa vähintään kaksi potenssia ei ole yhtä suuri kuin nolla ja kaikkien potenssien summa on yhtä suuri kuin p ) kutsutaan multinomikertoimeksi ja lasketaan kaavalla $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alpha ,\beta ,\gamma \ldots \nu$

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

Koska potenssit ovat tätä pienemmät , moninomikertoimen nimittäjä ei sisällä tekijöitä, jotka voisivat kumota, joten kaikki polynomin kertoimet ovat kerrannaisia . Näin ollen seuraava identiteetti on totta: $\alpha ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $s.$

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

jossa on polynomi, jolla on positiiviset kokonaislukukertoimet. $H(x,y,z,...,w)$

Olkoon nyt tässä identiteetissä (tässä n on muuttujien lukumäärä alkuperäisessä polynomilausekkeessa), on siis :n kerrannainen . Jos ei ole jaollinen alkuluvulla, niin [10] on jaollinen sillä . $x=y=...=w=1,H(1,1,1,...,1)=N,$ $n^{p}-n=Np$ $n(n^{p-1}-1)$ $s$ $n$ $p,$ $n^{{p-1}}-1$

Todistus induktiolla

Osoitetaan, että minkä tahansa alkuluvun p ja ei-negatiivisen kokonaisluvun a p − a on jaollinen p: llä . Todistamme induktiolla a :lla .

Pohja. Kun a = 0 , a p − a = 0 ja on jaollinen p :llä .

Siirtyminen. Olkoon väite tosi, kun a = k . Todistetaan se arvolle a = k + 1 .

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

Mutta k p − k on jaollinen p :llä induktiohypoteesin avulla. Muut termit sisältävät tekijän . Sillä , Tämän murtoluvun osoittaja on jaollinen p :llä ja nimittäjä on p :llä , joten se on jaollinen p :llä . Koska kaikki yksittäiset termit ovat jaollisia p :llä , on myös koko summa jaollinen p :llä . ${p \choose l}={p! \yli! (pl)!}$ $1\leqslant l\leqslant p-1$ ${p \valitse l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \valitse l}$

Negatiivisen a :n ja parittoman p : n kohdalla lause on helppo todistaa korvaamalla b = − a . Negatiivisille a ja p = 2 lauseen totuus seuraa lauseesta a 2 − a = a ( a − 1) [11] .

Todistus ryhmäteorialla

Yksi Fermat'n pienen lauseen yksinkertaisimmista todisteista perustuu ryhmäteorian Lagrangen lauseeseen , jonka mukaan äärellisen ryhmän elementin järjestys jakaa ryhmän järjestyksen.

Muista, että äärellisen ryhmän järjestys on sen alkioiden lukumäärä, ja elementin järjestys on sen asteen pienin luonnollinen eksponentti, joka on yhtä suuri kuin ryhmän yksikköelementti . $G$ $g\in G$ $e$ $G$

Antaa olla rajallinen ryhmä järjestystä . Koska elementtien järjestys jakaa , tästä seuraa, että . $G$ $n$ $g\in G$ $n$ $g^{n}=e$

Harkitse jäännösten kenttää modulo . Kokonaisluvun vähennys merkitään . Kentän nollasta poikkeavat elementit muodostavat kertolaskussa ryhmän. $\mathbb {Z} _{p}$ $s$ $a$ $a$ $\mathbb {Z} _{p}$

Tämän ryhmän järjestys on ilmeisesti . Sen yksittäinen elementti on . Tästä seuraa, että jokaiselle luvulle , joka ei ole jaollinen luvulla , mutta tämä tarkoittaa vain vertailua [1] $p-1$ $yksi$ $a$ $s$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Todistus modulaarista aritmetiikkaa käyttäen

Lemma. Jokaiselle alkuluvulle ja kokonaisluvulle , joka ei ole luvun kerrannainen , tulo ja luvut jaettuna jäännöksellä antavat samat luvut , mahdollisesti kirjoitettuna jossain eri järjestyksessä. $s$ $k$ $s$ $k$ $1,2,3,\ldots ,p-1$ $s$ $1,2,3,\ldots ,p-1,$

Todiste lemasta

Tulo ja mikään luku ei ole luvun kerrannainen , joten loppuosa ei voi olla . Kaikki jäännökset ovat erilaisia. Todistakaamme viimeinen väite ristiriitaisesti. Olkoon ja kaksi tuotetta ja anna kun jaettuna identtisillä jäännöksillä, niin ero on :n kerrannainen , mikä on mahdotonta, koska se ei ole :n kerrannainen . Yhteensä on erilaisia nollasta poikkeavia jäännöksiä jaosta . $k$ $1,2,3,\ldots ,p-1$ $s$ $0$ $a,b\in \{1,2,3,\ldots ,p-1\}$ $a\neq b$ $ak$ $bk$ $s$ $ak-bk=(ab)k$ $s$ $ab$ $s$ $p-1$ $s$

Koska yllä olevan lemman mukaan jäännökset lukujen a , 2 a , 3 a , ..., ( p − 1) a jakamisen jälkeen on luvun 1, 2, 3, ... permutaatioon asti . , p − 1 , sitten . Täältä . Viimeinen relaatio voidaan pelkistää arvoon ( p − 1)! , koska kaikki tekijät ovat koprime-lukuja, joiden kantaluku on p , tuloksena saadaan vaadittu lause [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}}$

Seuraukset ja yleistykset

Jos on alkuluku, yhtälö [13] on tosi kentässä . $s$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Jos on jokin muu alkuluku kuin 2 ja 5, niin luku, jonka desimaaliluku sisältää vain numeroita , on jaollinen luvulla . Tästä seuraa, että mille tahansa kokonaisluvulle , joka ei ole jaollinen 2:lla tai 5:llä, voit valita luvun, joka koostuu vain yhdeksästä ja joka on jaollinen luvulla . Tätä tosiasiaa käytetään jakomerkkien ja jaksollisten murtolukujen teoriassa [14] . $s$ $10^{p-1}-1$ $9$ $s$ $N$ $N$
Fermat'n Pienen lauseen avulla voit löytää muodon ja [15] lukujen alkujakajia . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
Fermatin pienen lauseen yleistys algebrallisiin lukuihin on Schönemannin vuonna 1839 laatima lause: olkoon d - asteisen normalisoidun polynomin juuret ja p alkuluku. Sitten [16] . $a_{1},\pisteet ,a_{d}$ $f\in \mathbb {Z} [x]$ $a_{1}^{p}+a_{2}^{p}+\pisteet +a_{d}^{p}\equiv a_{1}+\dots +a_{d}{\pmod {p))$
Fermat'n pieni lause sisältää Wilsonin lauseen : Luonnollinen luku on alkuluku silloin ja vain jos se on jaollinen p :llä . $p>1$ $(p-1)!+1$

Todiste Wilsonin lauseesta

Lukuteorian Lagrangen teoreema sanoo, että jos astepolynomi on jaollinen alkuluvulla muuttujan useammilla moduloarvoilla (eli joilla on erilaiset jäännökset jaettuna ) muuttujan arvoilla , niin se on jaollinen millä tahansa arvolla . $n$ $s$ $n$ $s$ $s$ $x$ $s$ $x$

Harkitse polynomia

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

missä on alkuluku.

s

Sitten löydämme:

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

Fermatin pienen lauseen perusteella kaikki nämä luvut ovat jaollisia alkuluvulla , joten vertailussa on epäjohdonmukaisia ratkaisuja. Toisaalta polynomin aste on vain tästä, mistä seuraa, että polynomi on jaollinen kaikille arvoille ja erityisesti $s$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $s$ $x,$ $x=0.$

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

Ja jos tämän lisäksi todistamme, että kaikille epäyksinkertaisille luonnollisille , paitsi , saamme lauseen todisteen. [17] $n$ $n = 4$ $(n-1)!\equiv 0{\pmod {n}}$

Sovellukset

Fermat-pseudoalkuluvut ja primaliteettitestaus

Fermat'n pikkulauseella voidaan testata, onko luku alkuluku: jos se ei ole jaollinen luvulla , niin se on yhdistelmäluku . Fermat'n pienen lauseen käänteinen käännös on kuitenkin yleensä virheellinen: jos ja ovat koalkilukuja ja ovat jaollisia luvulla , niin luku voi olla sekä alkuluku että yhdistelmä. Siinä tapauksessa, että on komposiitti, sitä kutsutaan Fermatin pseudosimpleiksi kantaan . $(a^{p}-a)$ $s$ $s$ $a$ $s$ $a^{p-1} - 1$ $s$ $s$ $s$ $a$

Esimerkiksi kiinalainen hypoteesi väittää, että se on alkuluku silloin ja vain jos [18] . Tässä on suora lausunto, että jos on alkuluku, niin , on Fermatin pienen lauseen erikoistapaus. Käänteinen väite, että jos , niin on yksinkertainen, on erikoistapaus Fermatin pienen lauseen käänteisestä. Tämä muunnos on väärä: Sarrus havaitsi vuonna 1820, että luku on jaollinen luvulla, koska se on jaollinen luvulla . Se on kuitenkin yhdistelmäluku : . Siten on pseudoalkuluku kannassa 2 [19] . $s$ $2^{p}\equiv 2{\pmod {p}}$ $s$ $2^{p}\equiv 2{\pmod {p}}$ $2^{p}\equiv 2{\pmod {p}}$ $s$ $N=2^{341-1}-1$ $341$ $N$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

Yleisessä tapauksessa myös Fermatin pienen lauseen käänteisluku epäonnistuu. Vastaesimerkki yleisessä tapauksessa ovat Carmichaelin luvut : nämä ovat lukuja , jotka ovat pseudoalkulukuja kaikille luvulle . Pienin Carmichaelin luku on 561. $s$ $a$ $a$ $s$

Koska Fermatin pienen lauseen käänteinen on virheellinen, sen ehdon täyttyminen ei takaa, että se on alkuluku . Siitä huolimatta Fermatin pieni lause on Fermatin primaalisuustestin perusta [20] . Fermat-testi on todennäköisyystesti: jos lause ei pidä paikkaansa, niin luku on täsmälleen yhdistetty, ja jos on, niin luku on alkuluku jollain todennäköisyydellä . Muiden todennäköisyysmenetelmien joukossa voidaan mainita: Solovay-Strassen-testi ja Miller-Rabin-testi , joista jälkimmäinen perustuu jossain määrin Fermatin pieneen lauseeseen [21] . On myös deterministinen algoritmi: Agrawal-Kayala-Saksen testi . $s$

Lisäksi seuraavat kaksi väitettä ovat totta. Jos pari tyydyttää vertailun , niin myös lukupari täyttää sen. Kaikille alkuluvuille ja sellaisille , että , arvo on Fermat-pseudoalkuluku kantaan [22] . ${\näyttötyyli (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$

RSA-algoritmi

Fermat's Little Theorem -lausetta käytetään myös RSA -salausalgoritmin oikeellisuuden todistamiseen [2] .

Katso myös

Muistiinpanot

↑ 1 2 Vinberg, 2008 , s. 43.
↑ 1 2 3 Sagalovich, 2014 , s. 34.
↑ Encyclopedia of Elementary Mathematics, kirja 1, Aritmetiikka, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961. - s. 280
↑ Z. I. Borevich, I. R. Shafarevich. Numeroteoria. - M .: Nauka, 1972. - 175 s.
↑ Gracian E. Alkuluvut . Pitkä tie äärettömyyteen. - De Agostini, 2014. - T. 3. - S. 45. - 148 s. — (Matematiikan maailma). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Numerot - tieteen kieli, 2008 , s. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Number Theory Through Inquiry Arkistoitu 16. syyskuuta 2012 Wayback Machinessa . - 2006. - s. 62-63.
↑ John J. O'Connor ja Edmund F. Robertson . Sir James Ivory on elämäkerta MacTutor- arkistossa .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Matematiikan oppikirjan sivujen takana: Aritmetiikka. Algebra. Geometria . - M . : Koulutus, 1996. - S. 30 . – 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Numerot - tieteen kieli, 2008 , s. 231-234.
↑ Vinberg, 2008 , s. 44.
↑ QUANTUM, 2000, nro 1, Senderov V, Spivak A. Fermat'n pieni lause.
↑ Akritas A. Tietokonealgebran perusteet sovellusten kanssa, s. 83.
↑ Danzig, T. Numerot - tieteen kieli, 2008 , s. 232-234.
↑ QUANTUM, 2000, nro 3, Senderov V, Spivak A Fermat'n pieni lause
↑ Vinberg, 2008 , s. 49.
↑ Danzig, T. Numerot ovat tieteen kieli, 2008 , s. 234-238.
↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, s. 103-105, ISBN 0-387-94457-5 .
↑ Weisstein EW Fermat Pseudoprime .. - 2005 ..
↑ Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Tietoturva: oppikirja. - M.: MIPT, 2011. - S. 236-237. — 262 s. Kanssa. — ISBN 978-5-7417-0377-9 .
↑ Williams HC Primality-testaus tietokoneella // Ars Combin. - 1978. - Voi. T. 5 , no. Ei. 12 . — s. 127-185 .
↑ Shitov Yu. A. Numeeriset menetelmät kryptografiassa.

Kirjallisuus

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Alkeismatematiikan tietosanakirja. Osa I: Aritmetiikka. – 1951.
Borevich Z. I., Shafarevich I. R. Lukuteoria . - M .: Nauka, 1972. - 510 s. Arkistoitu 8. tammikuuta 2011 Wayback Machinessa
Vinberg EB Fermat'n pieni lause ja sen yleistykset // Matem. valaistuminen - M . : MTSNMO :n kustantaja , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Fermatin pieni lause" . - Kvant , 1972. - Nro 10 . (linkki ei saatavilla)
Danzig, T. Numerot ovat tieteen kieli . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Lukuteorian algoritmiset ongelmat . - 1997. - Numero. 2 , nro kolmas sarja .
Sagalovich Yu. L. Johdatus algebrallisiin koodeihin - 3. painos, tarkistettu. ja ylimääräistä - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Fermat'n pieni lause // Kvant. - 2000. - Nro 1 .
Senderov V, Spivak A. Fermat'n pieni lause // Kvant. - 2000. - Nro 3 .