Fermats lille sætning

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

 

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

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

 

For eksempel, hvis  = 2 og  = 7, så 2 6 = 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 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  er et primtal, og  er et helt tal, der ikke kan deles med , er  deleligt med  .Dette kan oversættes med (forklaringer og formler tilføjet i parentes for lettere forståelse), som:Hvert primtal [  ] deler nødvendigvis en af kræfterne minus en af enhver [geometrisk] progression [  ] [det vil sige, der findes  sådan, at  deler  ], og eksponenten af denne magt [  ] deler den givne primære minus en [deler  ]. Når man har fundet den første magt [  ], 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  har den samme egenskab].Fermat overvejede ikke tilfældet, hvor  er et multiplum af  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  hvis og kun hvis  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 , 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  og ethvert heltal har , som er indbyrdes primisk med  ,

 

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

 

for alle heltal  og  . Dette følger af Eulers sætning, da hvis , så er  for et heltal , og man har

 

Hvis  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  .

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

 

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

 

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

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

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:

 

og for alle primer  deler  man har

 

så er  prime.

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

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

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

 

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  er et ulige primtal, og , med  ulige, så for hver  primtal til , enten , eller der findes  sådan, at  og Dette resultat kan udledes af Fermats lille sætning af det faktum, at hvis  er en ulige prim, så danner heltallet modulo  et endeligt felt, hvor  har nøjagtigt to kvadratrødder, 1 og -1.

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

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 

 
 
 
 
 
 

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

Kilder og henvisninger

 
 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 .

Sider uden gennemgået oversættelser
Matematiske sætninger