Fermats lille sætning

Fermats lille sætning er en sætning i talteori , der siger, at [1] :

Hvis er et primtal og er et heltal , der ikke er deleligt med , er deleligt med $s$ $-en$ $p,$ $a^{p-1}-1$ $s.$

I kongruensteoriens sprog : kongruent til 1 modulo a primtal . Formel notation: $a^{p-1}$ $s$ $a^{p-1}\equiv 1{\pmod {p}}$

For eksempel, hvis da og $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

Fermats lille sætning er et specialtilfælde af Eulers sætning [2] , som igen er et særtilfælde af Carmichaels sætning og Lagranges gruppesætning for endelige cykliske grupper . Sætningen blev fremsat uden bevis af Pierre Fermat , det første bevis blev givet af Leonhard Euler og Gottfried Wilhelm Leibniz .

Fermats lille sætning er blevet en af hovedsætningerne for forskning, ikke kun i teorien om heltal, men også på bredere områder [3] [4] .

Historie

Pierre Fermat formulerede den oprindelige sætning af sætningen i et brev fra 1640 til den franske matematiker Bernard Frenicle [5] :

Hvert primtal er ækvivalent med [original: måler ] en potens minus en med en hvilken som helst grundtal og en eksponent lig med det givne primtal minus en... Og dette udsagn er generelt sandt for alle grundtal og alle primtal. Jeg ville sende dig beviset, hvis det ikke var så længe.

Originaltekst (fr.)[ Visskjule] 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 lang. — Kilde: Fermat a Frenicle

Som et eksempel giver Fermat progressionen 3, 9, 27, 81, 243, 729... og primtallet 13. 13 deler 27 − 1 (eksponenten af 27 er 3, og 3 deler 13 − 1), hvilket indebærer, at 13 deler også 729 − 1 (eksponenten for 729 er 6 og er et multiplum af 3).

Fermat selv forlod sit teorem uden bevis. Den første matematiker, der fandt et bevis, var Gottfried Wilhelm Leibniz, hvis manuskripter indikerer, at han kendte beviset før 1683. Leibniz kendte ikke til Fermats resultat og opdagede sætningen uafhængigt [6] . Leibniz' værk blev dog ikke offentliggjort, og beviset blev offentliggjort af Euler i 1736 i Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio [7] . I 1806 offentliggjorde den skotske matematiker James Ivory et bevis baseret på det faktum, at hvis det løber gennem det fulde system af rester modulo , så for ethvert ikke-multiplet produkt også løber gennem det fulde system af rester modulo er denne idé grundlaget for moderne beviser [8] . $x$ $s$ $en,$ $p,$ $økse$ $p;$

Nummeret hedder Fermats private . Den russiske matematiker D. A. Grave foreslog, at Fermats kvotient aldrig er delelig med For primtal, der ikke overstiger 1000, er dette sandt, men et modeksempel blev hurtigt opdaget: for Fermats kvotient er delelig med 1093 [9] . ${\frac {a^{p-1}-1}{p))$ $s.$ $p=1093,a=2$

Alternativ formulering

Følgende formulering er kendetegnet ved fraværet af kravet om, at tallet ikke er deleligt med : $-en$ $s$

Hvis er et primtal og er et hvilket som helst heltal , så kan sammenlignes med modulo , det vil sige . $s$ $-en$ $a^{p}$ $-en$ $s$ $a^{p}\equiv a{\pmod {p}}$

For eksempel, hvis , derefter og . $a=7;p=5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

Det er let at vise, at denne formulering er reduceret til den originale. Så hvis er deleligt med , så og , dvs. . Hvis det ikke er deleligt med , så svarer udtrykket til udtrykket [2] . $-en$ $s$ $a\equiv 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $-en$ $s$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Både den primære og den alternative formulering kan bruges til at teste, om et givet tal er primtal (se nedenfor ), men den primære formulering er mere robust i den forstand, at den afviser flere sammensatte tal . Eksempel: Lad os tjekke, om det er et primtal. Lad B opnås i en alternativ formulering , og dette kan sammenlignes med 4 mod 6. Det vil sige, at tallet 6 ikke afvises, dets enkelthed bliver ikke tilbagevist. Hvis vi vender tilbage til den oprindelige sætning: , så , og dette er ikke sammenligneligt med 1 mod 6, som det burde være, hvis p er et primtal. Så den grundlæggende formulering er mere effektiv til at udslette sammensatte tal. $6$ $a=4.$ $4^{6}=4096=682\ gange 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\ gange 6+4$

Beviser

Bevis for sætningen foreslået af Leibniz

Overvej et homogent polynomium af grad p med n variable:

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

Åbner vi parenteserne, får vi koefficienten ved monomialet (hvor mindst to af potenserne ikke er lig med nul, og summen af alle potenserne er lig p ) kaldes multinomialkoefficienten og beregnes med formlen $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alfa ,\beta ,\gamma \ldots \nu$

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

Da potenserne er mindre end det, indeholder nævneren af den multinomiale koefficient ikke faktorer, der kan annullere, og derfor er alle koefficienterne for polynomiet multipla . Således er følgende identitet sand: $\alfa ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $s.$

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

hvor er et polynomium med positive heltalskoefficienter. $H(x,y,z,...,w)$

Lad nu i denne identitet så (her er n antallet af variabler i det oprindelige polynomium udtryk), derfor er et multiplum af . Hvis det ikke er deleligt med et primtal, så er [10] deleligt med det . $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$

Bevis ved induktion

Lad os bevise, at for ethvert primtal p og ikke-negativt heltal a , er a p − a deleligt med p . Vi beviser ved induktion på en .

Grundlag. For a = 0 er a p − a = 0 og er deleligt med p .

Overgang. Lad udsagnet være sandt for a = k . Lad os bevise det for 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 \choose l}

Men k p − k er deleligt med p ved induktionshypotesen. Resten af termerne indeholder faktoren . For , tælleren af denne brøk er delelig med p , og nævneren er coprime til p , derfor er delelig med p . Da alle individuelle led er delelige med p , er hele summen også delelig med p . ${p \vælg l}={p! \over l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \vælg l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}$

For negativ a og ulige p er sætningen let at bevise ved at erstatte b = − a . For negative a og p = 2 følger sætningens sandhed af a 2 − a = a ( a − 1) [11] .

Bevis ved hjælp af gruppeteori

Et af de enkleste beviser for Fermats lille sætning er baseret på en konsekvens af Lagranges sætning fra gruppeteori , der siger, at rækkefølgen af et element i en endelig gruppe deler rækkefølgen af gruppen.

Husk, at rækkefølgen af en endelig gruppe er antallet af dens elementer, og rækkefølgen af et element er den mindste naturlige eksponent for dens grad, der er lig med enhedselementet i gruppen . $G$ $g\in G$ $e$ $G$

Lad være en begrænset rækkefølge . Da elementrækkefølgen deler sig , følger det, at . $G$ $n$ $g\in G$ $n$ $g^{n}=e$

Overvej feltet af rester modulo . Fradraget af et heltal vil blive angivet med . De ikke-nul elementer i feltet danner en gruppe med hensyn til multiplikation. $\mathbb {Z} _{p}$ $s$ $-en$ $-en$ $\mathbb {Z} _{p}$

Rækkefølgen af denne gruppe er åbenlyst . Dens enkeltelement er . Det følger, at for hvert tal , der ikke er deleligt med , , men dette betyder blot sammenligning [1] $p-1$ $en$ $-en$ $s$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Bevis ved hjælp af modulær aritmetik

Lemma. For ethvert primtal og et heltal , ikke et multiplum af , giver produktet af og tallene, når de divideres med resten, de samme tal , muligvis skrevet i en anden rækkefølge. $s$ $k$ $s$ $k$ $1,2,3,\ldots,p-1$ $s$ $1,2,3,\ldprikker,p-1,$

Bevis for lemmaet

Produktet og nogen af tallene er ikke et multiplum af , derfor kan resten ikke være . Alle rester er forskellige. Lad os bevise den sidste påstand ved modsigelse. Lad ved og to produkter og giv når man dividerer med identiske rester, så er forskellen et multiplum af , hvilket er umuligt, da det ikke er et multiplum af . I alt er der forskellige rester, der ikke er nul fra division med . $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$

Da, ifølge ovenstående lemma, er resten efter at have divideret tallene a , 2 a , 3 a , ..., ( p − 1) a op til en permutation af tallet 1, 2, 3, ... , s − 1 , så . Herfra . Den sidste relation kan reduceres til ( p − 1)! , da alle faktorer er coprimtal med grundtal p , får vi som følge heraf den påkrævede sætning [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 og generaliseringer

Hvis er et primtal, så er ligheden [13] sand i feltet . $s$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Hvis er et andet primtal end 2 og 5, så er det tal, hvis decimalnotation kun indeholder cifre , deleligt med . Det følger heraf, at for ethvert heltal , der ikke er deleligt med enten 2 eller 5, kan du hente et tal, der kun består af ni, som er deleligt med . Dette faktum bruges i teorien om delelighedstegn og periodiske brøker [14] . $s$ $10^{p-1}-1$ $9$ $s$ $N$ $N$
Fermats lille sætning giver dig mulighed for at finde primtal divisorer af tal på formen og [15] . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
En generalisering af Fermats lille sætning til algebraiske tal er en sætning formuleret af Schönemann i 1839: lad være rødderne til et normaliseret polynomium af grad d og p være et primtal. Derefter [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 lille sætning indebærer Wilsons sætning : Et naturligt tal er primtal , hvis og kun hvis det er deleligt med p . $p>1$ $(p-1)!+1$

Bevis for Wilsons sætning

Lagrange-sætningen i talteorien siger, at hvis et polynomium af grad er deleligt med et primtal for mere end uforlignelige modulo -værdier (dvs. have forskellige rester, når de divideres med ) værdier af variablen , så er det deleligt med en hvilken som helst værdi . $n$ $s$ $n$ $s$ $s$ $x$ $s$ $x$

Overvej polynomiet

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

hvor er et primtal.

s

Så finder 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 af Fermats lille sætning er alle disse tal delelige med et primtal , så sammenligningen har inkongruente løsninger. På den anden side er graden af et polynomium kun heraf følger, at polynomiet er deleligt med for alle værdier og især for $s$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $s$ $x,$ $x=0.$

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

Og hvis vi ud over dette beviser, at for alle ikke-simple naturals , bortset fra , , så opnår vi beviset for sætningen. [17] $n$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Ansøgninger

Fermat pseudoprimer og primalitetstestning

Fermats lille sætning kan bruges til at teste om et tal er primtal: hvis det ikke er deleligt med , så er det et sammensat tal . Men det modsatte af Fermats lille sætning er generelt forkert: hvis og er coprimtal og er delelige med , så kan tallet være både primtal og sammensat. I tilfældet, hvornår er det sammensat, kaldes det Fermats pseudosimple til basen . $(a^{p}-a)$ $s$ $s$ $-en$ $s$ $a^{p-1} - 1$ $s$ $s$ $s$ $-en$

For eksempel siger den kinesiske hypotese , at det er et primtal, hvis og kun hvis [18] . Her er en direkte erklæring om, at hvis er primtal, så er , et specialtilfælde af Fermats lille sætning. Den omvendte påstand om, at hvis , så er enkel, er et specialtilfælde af inversionen af Fermats lille sætning. Denne konvertering er falsk: Sarrus fandt i 1820, at et tal er deleligt med , fordi det er deleligt med . Det er dog et sammensat tal : . Er således et pseudoprimtal i base 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$

I det generelle tilfælde fejler det omvendte af Fermats lille sætning også. Et modeksempel i det generelle tilfælde er Carmichael-tallene : disse er tal , der er pseudoprime i base for alle coprime til . Det mindste af Carmichaels tal er 561. $s$ $-en$ $-en$ $s$

På grund af det faktum, at det omvendte af Fermats lille sætning er forkert, garanterer opfyldelsen af dens betingelse ikke, at det er et primtal . Ikke desto mindre ligger Fermats lille sætning til grund for Fermat-testen for primalitet [20] . Fermat-testen er en probabilistisk primalitetstest: hvis sætningen ikke er sand, så er tallet nøjagtigt sammensat, og hvis det er, så er tallet prime med en vis sandsynlighed . Blandt andre probabilistiske metoder kan man bemærke: Solovay-Strassen-testen og Miller-Rabin-testen , sidstnævnte er til en vis grad afhængig af Fermats lille teorem [21] . Der er også en deterministisk algoritme: Agrawal-Kayala-Saksen test . $s$

Derudover er de følgende to udsagn sande. Hvis et par opfylder sammenligningen , så opfylder talparret også det. For ethvert primtal og enhver sådan , er værdien et Fermat-pseudoprimtal til 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}}$ $-en$

RSA-algoritme

Fermat's Little Theorem bruges også til at bevise rigtigheden af RSA -krypteringsalgoritmen [2] .

Se også

Noter

↑ 1 2 Vinberg, 2008 , s. 43.
↑ 1 2 3 Sagalovich, 2014 , s. 34.
↑ Encyclopedia of Elementary Mathematics, Bog 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 s.
↑ Gracian E. Primtal. Lang vej til det uendelige. - De Agostini, 2014. - T. 3. - S. 45. - 148 s. — (Matematikkens Verden). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Numbers - videnskabens sprog, 2008 , s. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Talteori gennem forespørgsel Arkiveret 16. september 2012 på Wayback Machine . - 2006. - s. 62-63.
↑ John J. O'Connor og Edmund F. Robertson . Sir James Ivory er en biografi på MacTutor- arkivet .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Bag siderne i en matematiklærebog: Aritmetik. Algebra. Geometri . - M . : Uddannelse, 1996. - S. 30 . - 320 sek. — ISBN 5-09-006575-6 .
↑ Danzig, T. Numbers - videnskabens sprog, 2008 , s. 231-234.
↑ Vinberg, 2008 , s. 44.
↑ QUANTUM, 2000, nr. 1, Senderov V, Spivak A. Fermats lille sætning.
↑ Akritas A. Grundlæggende om computeralgebra med applikationer, s. 83.
↑ Danzig, T. Numbers - videnskabens sprog, 2008 , s. 232-234.
↑ QUANTUM, 2000, nr. 3, Senderov V, Spivak A Fermat's Little Theorem
↑ Vinberg, 2008 , s. 49.
↑ Danzig, T. Tal er videnskabens sprog, 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. Informationssikkerhed: en lærebog. - M.: MIPT, 2011. - S. 236-237. — 262 s. Med. — ISBN 978-5-7417-0377-9 .
↑ Williams HC Primalitetstest på en computer // Ars Combin. - 1978. - Bd. T. 5 , nr. Ingen. 12 . — S. 127-185 .
↑ Shitov Yu. A. Numeriske metoder i kryptografi.

Litteratur

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Encyklopædi af elementær matematik. Bind I: Aritmetik. - 1951.
Borevich Z. I., Shafarevich I. R. Talteori . — M .: Nauka, 1972. — 510 s. Arkiveret 8. januar 2011 på Wayback Machine
Vinberg EB Fermats lille sætning og dens generaliseringer // Matem. oplysning - M . : Forlag af MTSNMO , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Fermats lille sætning" . - Kvant , 1972. - Nr. 10 . (utilgængeligt link)
Danzig, T. Tal er videnskabens sprog . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Algoritmiske problemer med talteori . - 1997. - Udgave. 2 , nr. tredje serie .
Sagalovich Yu. L. Introduktion til algebraiske koder - 3. udgave, revideret. og yderligere - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Fermats lille sætning // Kvant. - 2000. - Nr. 1 .
Senderov V, Spivak A. Fermats lille sætning // Kvant. - 2000. - Nr. 3 .