Fermats lilla sats

Fermats lilla sats är en sats i talteori som säger att [1] :

Om är ett primtal och är ett heltal som inte är delbart med då är delbart med $sid$ $a$ $p,$ $a^{p-1}-1$ $sid.$

På kongruensteorins språk : kongruent till 1 modulo a primtal . Formell notation: $a^{p-1}$ $sid$ $a^{p-1}\equiv 1{\pmod {p}}$

Till exempel om då och $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

Fermats lilla teorem är ett specialfall av Eulers sats [2] , som i sin tur är ett specialfall av Carmichaels sats och Lagranges gruppsats för ändliga cykliska grupper . Teoremet angavs utan bevis av Pierre Fermat , det första beviset gavs av Leonhard Euler och Gottfried Wilhelm Leibniz .

Fermats lilla sats har blivit en av huvudsatserna för forskning inte bara inom heltalsteorin, utan även inom vidare områden [3] [4] .

Historik

Pierre Fermat formulerade det ursprungliga uttalandet av satsen i ett brev från 1640 till den franske matematikern Bernard Frenicle [5] :

Varje primtal är ekvivalent med [original: mäter ] en potens minus ett med valfri bas och en exponent lika med det givna primtalet minus ett... Och detta påstående är i allmänhet sant för alla baser och alla primtal. Jag skulle skicka dig beviset om det inte var så länge.

Originaltext (fr.)[ visaDölj] 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 progressions et en tous nombres premiers ; de quoi je vous envoierois la demonstration, si je n'appréhendois d'être trop lång. — Källa: Fermat a Frenicle

Som ett exempel ger Fermat progressionen 3, 9, 27, 81, 243, 729... och primtalet 13. 13 delar 27 − 1 (exponenten för 27 är 3, och 3 delar 13 − 1), vilket innebär att 13 delar också 729 − 1 (exponenten för 729 är 6 och är en multipel av 3).

Fermat själv lämnade sitt teorem utan bevis. Den första matematikern som hittade ett bevis var Gottfried Wilhelm Leibniz, vars manuskript visar att han kände till beviset före 1683. Leibniz visste inte om Fermats resultat och upptäckte satsen självständigt [6] . Leibniz verk publicerades dock inte, och beviset publicerades av Euler 1736 i Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio [7] . År 1806 publicerade den skotske matematikern James Ivory ett bevis baserat på det faktum att om den går igenom hela systemet av rester modulo , så för alla icke-multipelprodukter också löper genom hela systemet av rester modulo är denna idé grunden för moderna bevis [8] . $x$ $sid$ $a,$ $p,$ $yxa$ $p;$

Numret heter Fermats privata . Den ryske matematikern D. A. Grave föreslog att Fermats kvot aldrig är delbar med För primtal som inte överstiger 1000 är detta sant, men ett motexempel upptäcktes snart: för Fermats kvot är delbar med 1093 [9] . ${\frac {a^{p-1}-1}{p))$ $sid.$ $p=1093,a=2$

Alternativ formulering

Följande formulering kännetecknas av frånvaron av kravet att talet inte är delbart med : $a$ $sid$

Om är ett primtal och är vilket heltal som helst , då är jämförbart med modulo , det vill säga . $sid$ $a$ $a^{p}$ $a$ $sid$ $a^{p}\equiv a{\pmod {p}}$

Till exempel om , då och . $a=7;p=5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

Det är lätt att visa att denna formulering är reducerad till den ursprungliga. Så, om är delbart med , då och , dvs. . Om det inte är delbart med , då är uttrycket ekvivalent med uttrycket [2] . $a$ $sid$ $a\ekvivalent 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $a$ $sid$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Både den primära och den alternativa formuleringen kan användas för att testa om ett givet tal är primtal (se nedan ), men den primära formuleringen är mer robust i den meningen att den avvisar fler sammansatta tal . Exempel: Låt oss kontrollera om det är ett primtal. Låt B erhållas i en alternativ formulering , och detta är jämförbart med 4 mod 6. Det vill säga siffran 6 förkastas inte, dess enkelhet motbevisas inte. Om vi återgår till den ursprungliga satsen: , då , och detta är inte jämförbart med 1 mod 6, som det borde vara om p är ett primtal. Så den grundläggande formuleringen är mer effektiv för att ta fram sammansatta siffror. $6$ $a=4.$ $4^{6}=4096=682\times 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\ gånger 6+4$

Bevis

Bevis för den sats som Leibniz föreslagit

Betrakta ett homogent polynom av grad p med n variabler:

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

Om vi öppnar parenteserna får vi koefficienten vid monomialen (där minst två av potenserna inte är lika med noll, och summan av alla potenser är lika med p ) kallas multinomkoefficienten och beräknas med formeln $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alfa ,\beta ,\gamma \ldots \nu$

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

Eftersom potenserna är mindre än så, innehåller nämnaren för den multinomiala koefficienten inte faktorer som kan upphäva, och därför är alla koefficienterna för polynomet multipler . Följande identitet är alltså sann: $\alfa ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $sid.$

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

där är ett polynom med positiva heltalskoefficienter. $H(x,y,z,...,w)$

Låt nu denna identitet då (här är n antalet variabler i det ursprungliga polynomuttrycket), är därför en multipel av . Om det inte är delbart med ett primtal, så är [10] delbart med det . $x=y=...=w=1,H(1,1,1,...,1)=N,$ $n^{p}-n=Np$ $n(n^{p-1}-1)$ $sid$ $n$ $p,$ $n^{{p-1}}-1$

Bevis genom induktion

Låt oss bevisa att för alla primtal p och icke-negativa heltal a , a p − a är delbart med p . Vi bevisar genom induktion på en .

Bas. För a = 0 är a p − a = 0 och är delbart med p .

Övergång. Låt påståendet vara sant för a = k . Låt oss bevisa det för a = k + 1 .

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

Men k p − k är delbart med p genom induktionshypotesen. Resten av termerna innehåller faktorn . För , täljaren för denna bråkdel är delbar med p , och nämnaren är coprime till p , därför är delbar med p . Eftersom alla individuella termer är delbara med p , är hela summan också delbar med p . ${p \choose l}={p! \över l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \välj l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}$

För negativa a och udda p är satsen lätt att bevisa genom att ersätta b = − a . För negativa a och p = 2 följer satsens sanning av a 2 − a = a ( a − 1) [11] .

Bevis med gruppteori

Ett av de enklaste bevisen för Fermats lilla sats är baserat på en följd av Lagranges sats från gruppteorin , som säger att ordningen för ett element i en finit grupp delar ordningen på gruppen.

Kom ihåg att ordningen för en ändlig grupp är antalet av dess element, och ordningen för ett element är den minsta naturliga exponenten av dess grad lika med enhetselementet i gruppen . $G$ $g\in G$ $e$ $G$

Låt vara en ändlig grupp av ordning . Eftersom elementordningen delar sig följer det att . $G$ $n$ $g\in G$ $n$ $g^{n}=e$

Tänk på området för rester modulo . Avdraget av ett heltal kommer att betecknas med . Fältets icke-nollelement bildar en grupp med avseende på multiplikation. $\mathbb {Z} _{p}$ $sid$ $a$ $a$ $\mathbb {Z} _{p}$

Ordningen för denna grupp är uppenbarligen . Dess enda element är . Det följer att för varje tal som inte är delbart med , , men detta betyder bara jämförelse [1] $p-1$ $ett$ $a$ $sid$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Bevis med modulär aritmetik

Lemma. För alla primtal och ett heltal , inte en multipel av , ger produkten av och talen, dividerat med resten, samma tal , eventuellt skrivna i någon annan ordning. $sid$ $k$ $sid$ $k$ $1,2,3,\ldots ,p-1$ $sid$ $1,2,3,\ldots ,p-1,$

Bevis på lemma

Produkten och något av talen är inte en multipel av , därför kan resten inte vara . Alla rester är olika. Låt oss bevisa det sista påståendet genom motsägelse. Låt vid och två produkter och ge när man dividerar med identiska rester, då är skillnaden en multipel av , vilket är omöjligt, eftersom det inte är en multipel av . Totalt finns det olika rester som inte är noll från division med . $k$ $1,2,3,\ldots ,p-1$ $sid$ $0$ $a,b\in \{1,2,3,\ldots ,p-1\}$ $a\neq b$ $ak$ $bk$ $sid$ $ak-bk=(ab)k$ $sid$ $ab$ $sid$ $p-1$ $sid$

Eftersom, enligt ovanstående lemma, återstoden efter division av talen a , 2 a , 3 a , ..., ( p − 1) a är upp till en permutation av talet 1, 2, 3, ... , p − 1 , sedan . Härifrån . Den sista relationen kan reduceras till ( p − 1)! , eftersom alla faktorer är samprimtal med bas p , som ett resultat får vi den obligatoriska satsen [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}}$

Konsekvenser och generaliseringar

Om är ett primtal, då är likheten [13] sann i fältet . $sid$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Om är ett annat primtal än 2 och 5, är talet vars decimalnotation endast innehåller siffror delbart med . Av detta följer att för vilket heltal som helst som inte är delbart med vare sig 2 eller 5, kan du plocka upp ett tal som endast består av nior, vilket är delbart med . Detta faktum används i teorin om tecken på delbarhet och periodiska bråk [14] . $sid$ $10^{p-1}-1$ $9$ $sid$ $N$ $N$
Fermats lilla sats låter dig hitta primtalsdelare för tal i formen och [15] . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
En generalisering av Fermats lilla sats till algebraiska tal är en sats formulerad av Schönemann 1839: låt vara rötterna till ett normaliserat polynom av grad d och p vara ett primtal. Sedan [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))$
Fermats lilla sats antyder Wilsons sats : Ett naturligt tal är primtal om och endast om det är delbart med p . $p>1$ $(p-1)!+1$

Bevis för Wilsons teorem

Lagrangesatsen i talteorin säger att om ett gradpolynom är delbart med ett primtal för mer än ojämförliga modulo (dvs. har olika rester när de divideras med ) värden av variabeln , så är det delbart med vilket värde som helst . $n$ $sid$ $n$ $sid$ $sid$ $x$ $sid$ $x$

Tänk på polynomet

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

var är ett primtal.

sid

Då finner vi:

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

I kraft av Fermats lilla teorem är alla dessa tal delbara med ett primtal , så jämförelsen har inkongruenta lösningar. Å andra sidan, graden av ett polynom är endast av detta följer att polynomet är delbart med för alla värden och i synnerhet för $sid$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $sid$ $x,$ $x=0.$

Betyder att $G(0)=[(p-1)!+1]\ekvivalent 0{\pmod {p}}.$

Och om vi utöver detta bevisar att för alla icke-enkla naturliga , förutom , , då får vi beviset för satsen. [17] $n$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Applikationer

Fermat pseudoprimer och primalitetstestning

Fermats lilla sats kan användas för att testa om ett tal är primtal: om det inte är delbart med , så är det ett sammansatt tal . Det omvända till Fermats lilla sats är dock generellt felaktigt: om och är samprimtal och är delbara med , då kan talet vara både primtal och sammansatt. I fallet när är komposit kallas det Fermats pseudosimple till basen . $(a^{p}-a)$ $sid$ $sid$ $a$ $sid$ $a^{p-1} - 1$ $sid$ $sid$ $sid$ $a$

Till exempel säger den kinesiska hypotesen att det är ett primtal om och endast om [18] . Här är ett direkt uttalande att om är primtal, då , är ett specialfall av Fermats lilla teorem. Det omvända påståendet att om , då är enkelt, är ett specialfall av inversionen av Fermats lilla teorem. Denna omvandling är falsk: Sarrus fann 1820 att ett tal är delbart med eftersom det är delbart med . Det är dock ett sammansatt nummer : . Således är ett pseudoprimtal i bas 2 [19] . $sid$ $2^{p}\equiv 2{\pmod {p}}$ $sid$ $2^{p}\equiv 2{\pmod {p}}$ $2^{p}\equiv 2{\pmod {p}}$ $sid$ $N=2^{341-1}-1$ $341$ $N$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

I det allmänna fallet misslyckas också inversen av Fermats lilla sats. Ett motexempel i det allmänna fallet är Carmichael-talen : dessa är tal som är pseudoprime i basen för alla coprime till . Det minsta av Carmichaels tal är 561. $sid$ $a$ $a$ $sid$

På grund av det faktum att motsatsen till Fermats lilla teorem är felaktig, garanterar inte uppfyllandet av dess villkor att det är ett primtal . Ändå ligger Fermats lilla teorem till grund för Fermattestet för primat [20] . Fermat-testet är ett probabilistiskt primalitetstest: om satsen inte är sann, är talet exakt sammansatt, och om det är det, är talet primtal med viss sannolikhet . Bland andra probabilistiska metoder kan man notera: Solovay-Strassen-testet och Miller-Rabin-testet , det senare förlitar sig i viss mån på Fermats lilla teorem [21] . Det finns också en deterministisk algoritm: Agrawal-Kayala-Saksen test . $sid$

Dessutom är följande två påståenden sanna. Om ett par uppfyller jämförelsen , så uppfyller även nummerparet det. För alla primtal och sådana att , värdet är en Fermat pseudoprime till basen [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$

RSA-algoritm

Fermats Little Theorem används också för att bevisa riktigheten av RSA- krypteringsalgoritmen [2] .

Se även

Anteckningar

↑ 1 2 Vinberg, 2008 , sid. 43.
↑ 1 2 3 Sagalovich, 2014 , sid. 34.
↑ Encyclopedia of Elementary Mathematics, Book 1, Arithmetic, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961.— S. 280
↑ Z. I. Borevich, I. R. Shafarevich. Talteori. — M .: Nauka, 1972. — 175 sid.
↑ Gracian E. Primtal . Lång väg till oändligheten. - De Agostini, 2014. - T. 3. - S. 45. - 148 sid. — (Matematikens värld). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Numbers - vetenskapens språk, 2008 , sid. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Number Theory Through Inquiry Arkiverad 16 september 2012 på Wayback Machine . - 2006. - s. 62-63.
↑ John J. O'Connor och Edmund F. Robertson . Sir James Ivory är en biografi i MacTutor- arkivet .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Bakom sidorna i en lärobok i matematik: Aritmetik. Algebra. Geometri . - M . : Utbildning, 1996. - S. 30 . — 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Numbers - vetenskapens språk, 2008 , sid. 231-234.
↑ Vinberg, 2008 , sid. 44.
↑ QUANTUM, 2000, nr 1, Senderov V, Spivak A. Fermats lilla sats.
↑ Akritas A. Grundläggande om datoralgebra med tillämpningar, s. 83.
↑ Danzig, T. Numbers - vetenskapens språk, 2008 , sid. 232-234.
↑ QUANTUM, 2000, nr 3, Senderov V, Spivak A Fermat's Little Theorem
↑ Vinberg, 2008 , sid. 49.
↑ Danzig, T. Numbers are the language of science, 2008 , sid. 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. Informationssäkerhet: en lärobok. - M.: MIPT, 2011. - S. 236-237. — 262 sid. Med. — ISBN 978-5-7417-0377-9 .
↑ Williams HC Primalitetstestning på en dator // Ars Combin. - 1978. - Vol. T. 5 , nr. Nej. 12 . — S. 127-185 .
↑ Shitov Yu. A. Numeriska metoder i kryptografi.

Litteratur

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Encyclopedia of elementary mathematics. Volym I: Aritmetik. — 1951.
Borevich Z. I., Shafarevich I. R. Talteori . — M .: Nauka, 1972. — 510 sid. Arkiverad 8 januari 2011 på Wayback Machine
Vinberg EB Fermats lilla sats och dess generaliseringar // Matem. upplysning - M . : Förlag av MTSNMO , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Fermats lilla sats" . - Kvant , 1972. - Nr 10 . (inte tillgänglig länk)
Danzig, T. Siffror är vetenskapens språk . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Algoritmiska problem med talteorin . - 1997. - Utgåva. 2 , nr tredje serien .
Sagalovich Yu. L. Introduktion till algebraiska koder - 3:e upplagan, reviderad. och ytterligare - M. : IPPI RAN , 2014. - 310 sid. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Fermats lilla sats // Kvant. - 2000. - Nr 1 .
Senderov V, Spivak A. Fermats lilla sats // Kvant. - 2000. - Nr 3 .