Fermats lille sætning

Fermats lille sætning siger, at hvis Skabelon:Mvar er et primtal, så gælder for ethvert heltal Skabelon:Mvar, at tallet Skabelon:Math er et heltalligt multiplum af Skabelon:Mvar . I notationen af modulær aritmetik udtrykkes dette som

$a^p\equiv a(\mathrm{mod}p).$

For eksempel, hvis Skabelon:Mvar = 2 og Skabelon:Mvar = 7, så 2 ⁷ = 128 og 128 - 2 = 126 = 7 × 18 er et heltalsmultipel på 7.

Hvis Skabelon:Mvar ikke kan deles med Skabelon:Mvar, svarer Fermats lille sætning til udsagnet om, at Skabelon:Math er et heltalligt multiplum af Skabelon:Mvar - eller udtrykt i modulær aritmetisk symbolsprog:

$a^{p-1}\equiv 1(\mathrm{mod}p).$

For eksempel, hvis Skabelon:Mvar = 2 og Skabelon:Mvar = 7, så 2 ⁶ = 64 og 64 - 1 = 63 = 7 × 9 er således et multiplum af 7.

Fermats lille sætning er grundlaget for Fermat-primalitetstesten og er et af de grundlæggende resultater af elementær talteori . Teoremet er opkaldt efter Pierre de Fermat, der fremsagde det i 1640. Det kaldes den "lille sætning" for at skelne den fra Fermats sidste sætning, som også kaldes den "store" sætning.

Historie

Pierre de Fermat

Pierre de Fermat fremsatte først sætningen i et brev dateret 18. oktober 1640 til sin ven og fortrolige Frénicle de Bessy . Hans formulering svarer til følgende:

Hvis Skabelon:Mvar er et primtal, og Skabelon:Mvar er et helt tal, der ikke kan deles med Skabelon:Mvar, er Skabelon:Math deleligt med Skabelon:Mvar .

Dette kan oversættes med (forklaringer og formler tilføjet i parentes for lettere forståelse), som:

Hvert primtal [ Skabelon:Mvar ] deler nødvendigvis en af kræfterne minus en af enhver [geometrisk] progression [ Skabelon:Math ] [det vil sige, der findes Skabelon:Mvar sådan, at Skabelon:Mvar deler Skabelon:Math ], og eksponenten af denne magt [ Skabelon:Mvar ] deler den givne primære minus en [deler Skabelon:Math ]. Når man har fundet den første magt [ Skabelon:Mvar ], der tilfredsstiller spørgsmålet, tilfredsstiller alle dem, hvis eksponenter er multipla af eksponenten af den første, spørgsmålet [det vil sige, at alle multipla af den første Skabelon:Mvar har den samme egenskab].

Fermat overvejede ikke tilfældet, hvor Skabelon:Mvar er et multiplum af Skabelon:Mvar og beviste heller ikke sin påstand, men kun med angivelse af:

(Og dette forslag gælder generelt for alle serier [ sic ] og for alle primtal; jeg vil sende dig en demonstration af det, hvis jeg ikke frygtede at fortsætte for længe. )

Euler var den første, der offentliggjorde et bevis, hvilket kom i 1736 i en artikel med titlen "Theorematum Quorundam annonce Numeros Primos Spectantium demonstratio" i Proceedings of St. Petersburg Academy, men Leibniz havde givet stort set den samme bevis i en upubliceret manuskript fra engang før 1683. Udtrykket "Fermats lille sætning" blev sandsynligvis først brugt på tryk i 1913 i Zahlentheorie af Kurt Hensel :

(Der findes en grundlæggende sætning i enhver begrænset gruppe, der normalt kaldes Fermats lille sætning, fordi Fermat var den første til at bevise en meget speciel del af den. )

En tidlig brug på engelsk forekommer i AA Albert 's Modern Higher Algebra (1937), der henviser til "den såkaldte' lille 'Fermat-sætning" på side 206.

Yderligere historie

Nogle matematikere stillede uafhængigt den relaterede hypotese (undertiden forkert kaldet den kinesiske hypotese), at Skabelon:Math hvis og kun hvis Skabelon:Mvar er primær. Faktisk er "hvis" -delen sand, og det er et specielt tilfælde af Fermats lille sætning. Imidlertid er "kun hvis" -delen falsk: For eksempel Skabelon:Math, men 341 = 11 × 31 er en pseudoprim . Se nedenfor .

Beviser

Flere beviser for Fermats lille sætning er kendt. Det er ofte bevist som en følge af Eulers sætning .

Generaliseringer

Eulers sætning er en generalisering af Fermats lille sætning: for ethvert modul Skabelon:Mvar og ethvert heltal har Skabelon:Mvar, som er indbyrdes primisk med Skabelon:Mvar ,

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

hvor Skabelon:Math betegner Eulers totientfunktion (som tæller heltalene fra 1 til Skabelon:Mvar der er coprime til Skabelon:Mvar ). Fermats lille sætning er faktisk et specielt tilfælde, for hvis Skabelon:Mvar er et primtal, så er Skabelon:Math .

$x\equiv y(\mathrm{mod}\phi (n))\text{implies}{a}^x\equiv a^y(\mathrm{mod}n),$

for alle heltal Skabelon:Mvar og Skabelon:Mvar . Dette følger af Eulers sætning, da hvis $x\equiv y(\mathrm{mod}\phi (n))$, så er Skabelon:Math for et heltal Skabelon:Mvar, og man har

$a^x=a^{y+\phi (n)k}=a^y(a^{\phi (n)}{)}^k\equiv a^y{1}^k\equiv a^y(\mathrm{mod}n).$

Hvis Skabelon:Mvar er primær, er dette også en følge af Fermats lille sætning. Dette bruges i vid udstrækning i modulær aritmetik, fordi dette gør det muligt at reducere modulær eksponentiering med store eksponenter til eksponenter mindre end Skabelon:Mvar .

Hvis Skabelon:Mvar ikke er primær, bruges dette i kryptografi med offentlig nøgle, typisk i RSA-kryptosystemet på følgende måde: hvis

$y=x^e(\mathrm{mod}n),$

at hente Skabelon:Mvar fra værdierne Skabelon:Mvar og Skabelon:Mvar er let, hvis man kender Skabelon:Math . Faktisk tillader den udvidede euklidiske algoritme at beregne det modulære inverse af Skabelon:Mvar modulo Skabelon:Math, det vil sige heltal Skabelon:Mvar sådan Skabelon:Nowrap Den følger det

$x\equiv x^{ef}\equiv (x^e{)}^f\equiv y^f(\mathrm{mod}n).$

På den anden side, hvis Skabelon:Math er produktet af to forskellige primtal, så er Skabelon:Math . I dette tilfælde er det lige så vanskeligt at Skabelon:Mvar fra Skabelon:Mvar og Skabelon:Mvar Skabelon:Math (dette er ikke bevist, men ingen algoritme er kendt for computing Skabelon:Mvar uden at kende Skabelon:Math ). Ved kun at kende Skabelon:Mvar har beregningen af Skabelon:Math i det væsentlige den samme vanskelighed som faktoriseringen af Skabelon:Mvar, da Skabelon:Math, og omvendt er faktorerne Skabelon:Mvar og Skabelon:Mvar de ( heltal) opløsninger af ligningen Skabelon:Math .

Grundideen med RSA-kryptosystem er således: Hvis en meddelelse Skabelon:Mvar er krypteret som Skabelon:Math ved hjælp af offentlige værdier på Skabelon:Mvar og Skabelon:Mvar, kan den med den nuværende viden ikke dekrypteres uden at finde den (hemmelige) faktorer Skabelon:Mvar og Skabelon:Mvar for Skabelon:Mvar .

Fermats lille sætning er også relateret til Carmichael-funktionen og Carmichaels sætning såvel som til Lagranges sætning i gruppeteori .

Diskussion

Det modsatte af Fermats lille sætning er generelt ikke sandt, da det mislykkes for Carmichael-tal . Imidlertid er en lidt stærkere form for sætningen sand, og den er kendt som Lehmer's sætning. Teoremet er som følger:

$a^{p-1}\equiv 1(\mathrm{mod}p)$

og for alle primer Skabelon:Mvar deler Skabelon:Math man har

$a^{(p-1)/q}\equiv ̸1(\mathrm{mod}p),$

så er Skabelon:Mvar prime.

Denne sætning danner grundlaget for Lucas primality test, en vigtig primality test .

Pseudoprimer

Hvis Skabelon:Mvar og Skabelon:Mvar er coprime-tal, således at Skabelon:Math kan deles med Skabelon:Mvar, Skabelon:Mvar ikke at være primær. Hvis det ikke er tilfældet, kaldes Skabelon:Mvar en (Fermat) pseudoprim til at basere Skabelon:Mvar . Den første pseudoprim til base 2 blev fundet i 1820 af Pierre Frédéric Sarrus : 341 = 11 × 31.

Et tal Skabelon:Mvar der er et Fermat-pseudoprime, der baserer Skabelon:Mvar for hvert tal, Skabelon:Mvar coprime til Skabelon:Mvar kaldes et Carmichael-nummer (f.eks. 561). Alternativt kan ethvert tal Skabelon:Mvar tilfredsstille ligestillingen

$\gcd (p,\sum _{a=1}^{p-1}{a}^{p-1})=1$

er enten et primtal eller et Carmichael-tal.

Miller – Rabin-test

Miller-Rabin-primality-testen bruger følgende udvidelse af Fermats lille sætning:

Hvis Skabelon:Mvar er et ulige primtal, og Skabelon:Math, med Skabelon:Mvar ulige, så for hver Skabelon:Mvar primtal til Skabelon:Mvar, enten Skabelon:Math, eller der findes Skabelon:Mvar sådan, at Skabelon:Math og Skabelon:Math

Dette resultat kan udledes af Fermats lille sætning af det faktum, at hvis Skabelon:Mvar er en ulige prim, så danner heltallet modulo Skabelon:Mvar et endeligt felt, hvor Skabelon:Math har nøjagtigt to kvadratrødder, 1 og -1.

Miller – Rabin-testen bruger denne egenskab på følgende måde: givet Skabelon:Math, med Skabelon:Mvar ulige, et ulige heltal, for hvilket primalitet skal testes, vælg tilfældigt Skabelon:Mvar sådan, at Skabelon:Math ; derefter beregne Skabelon:Math ; hvis Skabelon:Mvar ikke er 1 eller −1, så firkant det gentagne gange modulo Skabelon:Mvar indtil du får 1, −1 eller har kvadreret Skabelon:Mvar gange. Hvis Skabelon:Math og −1 ikke er opnået, er Skabelon:Mvar ikke prime. Ellers kan Skabelon:Mvar være prime eller ej. Hvis Skabelon:Mvar ikke er primær, er sandsynligheden for, at dette bevises ved testen, større end 1/4. Derfor er Skabelon:Mvar ikke er prime Skabelon:Mvar ikke-endelige tilfældige tests Skabelon:Math og kan således gøres så lavt som ønsket ved at øge Skabelon:Mvar .

Sammenfattende viser testen enten, at et tal ikke er prime, eller hævder, at det er prime med en sandsynlighed for fejl, der kan vælges så lavt som ønsket. Testen er meget enkel at implementere og beregningsmæssigt mere effektiv end alle kendte deterministiske tests. Derfor bruges det generelt, før der påbegyndes et bevis på, at det er primalt.

Referencer

• Skabelon:Kilde
• Skabelon:Kilde
• Skabelon:Kilde
• Skabelon:Kilde
• Skabelon:Kilde
• Skabelon:Kilde

• Paulo Ribenboim (1995). The New Book of Prime Number Records (3. udg. ). New York: Springer-Verlag.Skabelon:ISBNISBN 0-387-94457-5 . pp. 22–25, 49.

Kilder og henvisninger

• Skabelon:Commonscat
• János Bolyai og pseudoprimerne (på ungarsk)
• Fermats lille sætning ved knuden
• Euler-funktion og sætning ved knuden
• Fermats lille sætning og Sophies bevis
• Weisstein, Eric W. "Fermats lille sætning" . MathWorld .
• Weisstein, Eric W. "Fermat's Little Theorem Converse" . MathWorld .