Se kilde til Fermats lille sætning

'''Fermats lille sætning''' siger, at hvis {{Mvar|p}} er et [[primtal]], så gælder for ethvert [[heltal]] {{Mvar|a}}, at tallet {{Math|''a''<sup>''p''</sup> − ''a''}} er et heltalligt multiplum af {{Mvar|p}} . I notationen af modulær aritmetik udtrykkes dette som

: <math>a^p \equiv a \pmod p.</math>

For eksempel, hvis {{Mvar|a}} = 2 og {{Mvar|p}} = 7, så 2 <sup>7</sup> = 128 og 128&nbsp;-&nbsp;2 = 126 = 7 × 18 er et heltalsmultipel på 7.

Hvis {{Mvar|a}} ikke kan deles med {{Mvar|p}}, svarer Fermats lille sætning til udsagnet om, at {{Math|''a''<sup>''p'' − 1</sup> − 1}} er et heltalligt multiplum af {{Mvar|p}} - eller udtrykt i modulær aritmetisk symbolsprog: <ref>{{Harvnb|Long|1972}}.</ref> <ref>{{Harvnb|Pettofrezzo|Byrkit|1970}}.</ref>

: <math>a^{p-1} \equiv 1 \pmod p.</math>

For eksempel, hvis {{Mvar|a}} = 2 og {{Mvar|p}} = 7, så 2 <sup>6</sup> = 64 og 64&nbsp;-&nbsp;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 [[Talteori|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. <ref name="Burton">{{Harvnb|Burton|2011}}.</ref>

== Historie ==
[[Fil:Pierre_de_Fermat.jpg|right|thumb| 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: <ref name="Burton">{{Harvnb|Burton|2011}}.</ref><blockquote>Hvis {{Mvar|p}} er et primtal, og {{Mvar|a}} er et helt tal, der ikke kan deles med {{Mvar|p}}, er {{Math|''a''<sup> ''p'' − 1</sup> − 1}} deleligt med {{Mvar|p}} .</blockquote><blockquote>{{Lang|fr|Tout nombre premier mesure infailliblement une des puissances <math>-1</math> de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné <math>-1</math>; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.}}</blockquote>Dette kan oversættes med (forklaringer og formler tilføjet i parentes for lettere forståelse), som:<blockquote>Hvert primtal [ {{Mvar|p}} ] deler nødvendigvis en af kræfterne minus en af enhver [geometrisk] [[Geometrisk række|progression]] [ {{Math|''a'', ''a''<sup>2</sup>, ''a''<sup>3</sup>, ...}} ] [det vil sige, der findes {{Mvar|t}} sådan, at {{Mvar|p}} deler {{Math|''a<sup>t</sup>'' – 1}} ], og eksponenten af denne magt [ {{Mvar|t}} ] deler den givne primære minus en [deler {{Math|''p'' – 1}} ]. Når man har fundet den første magt [ {{Mvar|t}} ], 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 {{Mvar|t}} har den samme egenskab].</blockquote>Fermat overvejede ikke tilfældet, hvor {{Mvar|a}} er et multiplum af {{Mvar|p}} og beviste heller ikke sin påstand, men kun med angivelse af: <ref>{{Kilde|fornavn=Pierre|efternavn=Fermat|titel=Oeuvres de Fermat. Tome 2: Correspondance|redaktør-efternavn=Tannery|år=1894|sted=Paris|udgiver=Gauthier-Villars|url=https://archive.org/stream/oeuvresdefermat02ferm#page/206/mode/2up|sider=206–212}} (in French)</ref><blockquote>{{Lang|fr|Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.}}</blockquote><blockquote>(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. ) <ref>{{Harvnb|Mahoney|1994}} for the English translation</ref></blockquote>[[Leonhard Euler|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, <ref>{{Harvnb|Ore|1988}}</ref> men [[Gottfried Wilhelm Leibniz|Leibniz]] havde givet stort set den samme bevis i en upubliceret manuskript fra engang før 1683. <ref name="Burton">{{Harvnb|Burton|2011}}.</ref>

Udtrykket "Fermats lille sætning" blev sandsynligvis først brugt på tryk i 1913 i ''Zahlentheorie'' af Kurt Hensel :<blockquote>{{Lang|de|Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.}}</blockquote><blockquote>(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. )</blockquote>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. <ref>{{Harvnb|Albert|2015|p=206}}</ref>

=== Yderligere historie ===
Nogle matematikere stillede uafhængigt den relaterede hypotese (undertiden forkert kaldet den kinesiske hypotese), at {{Math|2<sup>''p''</sup> ≡ 2 (mod ''p'')}} hvis og kun hvis {{Mvar|p}} 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 {{Math|2<sup>341</sup> ≡ 2 (mod 341)}}, men 341&nbsp;=&nbsp;11&nbsp;×&nbsp;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 {{Mvar|n}} og ethvert heltal har {{Mvar|a}}, som er indbyrdes primisk med {{Mvar|n}} ,

: <math>a^{\varphi (n)} \equiv 1 \pmod n,</math>

hvor {{Math|''φ''(''n'')}} betegner [[Eulers totientfunktion]] (som tæller heltalene fra 1 til {{Mvar|n}} der er coprime til {{Mvar|n}} ). Fermats lille sætning er faktisk et specielt tilfælde, for hvis {{Mvar|n}} er et primtal, så er {{Math|1=''φ''(''n'') = ''n'' − 1}} .

: <math>x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, </math>

for alle heltal {{Mvar|x}} og {{Mvar|y}} . Dette følger af Eulers sætning, da hvis <math>x \equiv y \pmod{\varphi(n)}</math>, så er {{Math|1=''x'' = ''y'' + ''kφ''(''n'')}} for et heltal {{Mvar|k}}, og man har

: <math>a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.</math>

Hvis {{Mvar|n}} 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 {{Mvar|n}} .

Hvis {{Mvar|n}} ikke er primær, bruges dette i kryptografi med offentlig nøgle, typisk i [[RSA|RSA-kryptosystemet]] på følgende måde: <ref>{{Kilde|fornavn=Wade|efternavn=Trappe|fornavn2=Lawrence C.|efternavn2=Washington|titel=Introduction to Cryptography with Coding Theory|år=2002|udgiver=Prentice-Hall|isbn=978-0-13-061814-6}}</ref> hvis

: <math>y=x^e\pmod n,</math>

at hente {{Mvar|x}} fra værdierne {{Mvar|e}} og {{Mvar|n}} er let, hvis man kender {{Math|''φ''(''n'')}} . Faktisk tillader den udvidede euklidiske algoritme at beregne det modulære inverse af {{Mvar|e}} modulo {{Math|''φ''(''n'')}}, det vil sige heltal {{Mvar|f}} sådan {{Nowrap|<math>ef\equiv 1\pmod{\varphi(n)}</math>.}} Den følger det

: <math>x\equiv x^{ef}\equiv (x^e)^f \equiv y^f \pmod n.</math>

På den anden side, hvis {{Math|1=''n'' = ''pq''}} er produktet af to forskellige primtal, så er {{Math|1=''φ''(''n'') = (''p'' − 1)(''q'' − 1)}} . I dette tilfælde er det lige så vanskeligt at {{Mvar|f}} fra {{Mvar|n}} og {{Mvar|e}} {{Math|''φ''(''n'')}} (dette er ikke bevist, men ingen algoritme er kendt for computing {{Mvar|f}} uden at kende {{Math|''φ''(''n'')}} ). Ved kun at kende {{Mvar|n}} har beregningen af {{Math|''φ''(''n'')}} i det væsentlige den samme vanskelighed som faktoriseringen af {{Mvar|n}}, da {{Math|1=''φ''(''n'') = (''p'' − 1)(''q'' − 1)}}, og omvendt er faktorerne {{Mvar|p}} og {{Mvar|q}} de ( heltal) opløsninger af ligningen {{Math|''x''{{sup|2}} – (''n'' − ''φ''(''n'') + 1) ''x'' + ''n'' {{=}} 0}} .

Grundideen med RSA-kryptosystem er således: Hvis en meddelelse {{Mvar|x}} er krypteret som {{Math|1=''y'' = ''x<sup>e</sup>''  (mod ''n'')}} ved hjælp af offentlige værdier på {{Mvar|n}} og {{Mvar|e}}, kan den med den nuværende viden ikke dekrypteres uden at finde den (hemmelige) faktorer {{Mvar|p}} og {{Mvar|q}} for {{Mvar|n}} .

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:

: <math> a^{p-1}\equiv 1\pmod p </math>

og for alle primer {{Mvar|q}} deler {{Math|''p'' − 1}} man har

: <math> a^{(p-1)/q}\not\equiv 1\pmod p, </math>

så er {{Mvar|p}} prime.

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

== Pseudoprimer ==
Hvis {{Mvar|a}} og {{Mvar|p}} er coprime-tal, således at {{Math|''a''<sup>''p''−1</sup> − 1}} kan deles med {{Mvar|p}}, {{Mvar|p}} ikke at være primær. Hvis det ikke er tilfældet, kaldes {{Mvar|p}} ''en (Fermat) pseudoprim'' til at basere {{Mvar|a}} . Den første pseudoprim til base 2 blev fundet i 1820 af Pierre Frédéric Sarrus : 341 = 11&nbsp;×&nbsp;31.

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

: <math>\gcd\left(p, \sum_{a=1}^{p-1} a^{p-1}\right)=1</math>

er enten et primtal eller et Carmichael-tal.

== Miller – Rabin-test ==
Miller-Rabin-primality-testen bruger følgende udvidelse af Fermats lille sætning: <ref>{{Kilde bog|kapitel=4.5.1. Lemma (Roots of unity modulo a prime)|kapitel-url=https://books.google.com/books?id=nQVZAgAAQBAJ&q=The+Miller%E2%80%93Rabin+primality+test+uses+the+following+extension+of+Fermat's+little+theorem&pg=PA144|titel=Primality Testing for Beginners|efternavn=Rempe-Gillen|fornavn=Lasse|efternavn2=Waldecker|fornavn2=Rebecca|forfatter2link=Rebecca Waldecker|dato=2013-12-11|udgiver=American Mathematical Soc.|isbn=9780821898833|sprog=en}}</ref><blockquote>Hvis {{Mvar|p}} er et ulige primtal, og {{Math|1=''p'' – 1 = 2<sup>''s''</sup> ''d''}}, med {{Mvar|d}} ulige, så for hver {{Mvar|a}} primtal til {{Mvar|p}}, enten {{Math|''a''<sup>''d''</sup> ≡ 1 mod ''p''}}, eller der findes {{Mvar|t}} sådan, at {{Math|0 ≤ ''t'' < s}} og {{Math|''a''<sup>2<sup>''t''</sup>''d''</sup> ≡ −1 mod ''p''}}</blockquote>Dette resultat kan udledes af Fermats lille sætning af det faktum, at hvis {{Mvar|p}} er en ulige prim, så danner heltallet modulo {{Mvar|p}} et endeligt felt, hvor {{Math|1}} har nøjagtigt to kvadratrødder, 1 og -1.

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

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 ==

* {{Kilde|efternavn=Albert|fornavn=A. Adrian|forfatterlink=Abraham Adrian Albert|titel=Modern higher algebra|url={{Google books|iVwZCgAAQBAJ|Modern higher algebra|page=206|plainurl=yes}}|udgiver=[[Cambridge University Press]]|isbn=978-1-107-54462-8|år=2015}}
* {{Kilde|fornavn=David M.|efternavn=Burton|titel=The History of Mathematics / An Introduction|udgave=7th|udgiver=McGraw-Hill|år=2011|isbn=978-0-07-338315-6}}
* {{Kilde|efternavn=Long|fornavn=Calvin T.|år=1972|titel=Elementary Introduction to Number Theory|udgave=2nd|udgiver=[[D. C. Heath and Company]]|sted=Lexington|lccn=77171950}}
* {{Kilde|efternavn=Mahoney|fornavn=Michael Sean|titel=The Mathematical Career of Pierre de Fermat, 1601–1665|år=1994|udgave=2nd|udgiver=Princeton University Press|isbn=978-0-691-03666-3}}
* {{Kilde|fornavn=Oystein|efternavn=Ore|titel=Number Theory and Its History|år=1988|udgiver=Dover|isbn=978-0-486-65620-5|url=https://archive.org/details/numbertheoryitsh0000orey}}
* {{Kilde|efternavn=Pettofrezzo|fornavn=Anthony J.|efternavn2=Byrkit|fornavn2=Donald R.|år=1970|titel=Elements of Number Theory|udgiver=[[Prentice Hall]]|sted=Englewood Cliffs|lccn=71081766}}

* Paulo Ribenboim (1995). ''The New Book of Prime Number Records'' (3. udg. ). New York: Springer-Verlag.{{ISBN|0-387-94457-5}}[[ISBN (identifier)|ISBN]]&nbsp;[[Speciel:BookSources/0-387-94457-5|0-387-94457-5]] . pp.&nbsp;22–25, 49.

==Kilder og henvisninger==
{{reflist}}
* {{Commonscat}}
* [https://web.archive.org/web/20041022022031/http://bolyai.port5.com/kisfermat.htm János Bolyai og pseudoprimerne] (på ungarsk)
* [http://www.cut-the-knot.org/blue/Fermat.shtml Fermats lille sætning] ved knuden
* [http://www.cut-the-knot.org/blue/Euler.shtml Euler-funktion og sætning] ved knuden
* [http://fermatslasttheorem.blogspot.com/2005/08/fermats-little-theorem.html Fermats lille sætning og Sophies bevis]
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> Weisstein, Eric W. "Fermats lille sætning" . MathWorld .
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> Weisstein, Eric W. "Fermat's Little Theorem Converse" . MathWorld .

[[Kategori:Sider uden gennemgået oversættelser]]
[[Kategori:Matematiske sætninger]]