Fermat kis tétele

A matematika , kis Fermat-tétel eredménye a moduláris aritmetika , ami szintén ki lehet mutatni az eszközöket az elemi számtani .

Ez a következőképpen hangzik: „Ha p egy prímszám , és ha a jelentése egész szám, nem osztható p , akkor egy  p -1  - 1 egy több a p  ”, más szóval (azonos körülmények között a a és p ) , egy  p -1 van kongruens 1 modulo p  :

.

Az ekvivalens állítás: „ha p prímszám, és ha egy olyan bármilyen egész szám , akkor a  p  - a többszöröse p  ”:

.

Nevét Pierre de Fermatnak köszönheti , aki 1640-ben nyilatkozta először .

Ez számos alkalmazás, mind a moduláris aritmetika és a kriptográfia .

Történelem

Az első ismert megjelenése a nyilatkozatot ennek a tételnek származik levele Fermat hogy Frénicle de Bessy kelt1640. október, amelyet fia, Sámuel adott ki 1679-ben a Varia Operában . Ezt olvashatjuk: „Bármely prímszám tévedhetetlenül méri bármelyik progresszió egyik erejét - 1, és az említett hatvány kitevője az adott prímszám részszorosa - 1; és miután megtaláltuk az első hatalmat, amely kielégíti a kérdést, mindazok, akiknek kitevői az első kitevőjének többszörösei, továbbra is kielégítik a kérdést. » , Azaz a modern értelemben minden prímszám p és bármennyi egy (prím p ), létezik egy egész t úgy, hogy p osztója a t -1 - és, t pedig a legkisebb egész szám eleget ennek, t osztja a p - 1 értéket, és a t összes n többszöröse igazolja, hogy p osztja az n - 1 értéket.

Azonnal levezetjük a bevezetőben megadott állítást, és kölcsönösen könnyen levezetjük belőle a Fermat által adott pontosabb állítást. Mint levelezésében szokás, Fermat semmilyen bizonyítékot nem ad erről az eredményről, sőt, mint néha, az erre vonatkozó jelzésekről sem, de pontosítja: "És ez a tétel általában minden progresszióban és minden számban igaz. Először; amelyből elküldöm neked a demonstrációt, ha nem félek, hogy túl sokáig tart. "

Ekkor szokás volt, hogy a tételek igazolását nem tették közzé. Így Leibniz 1683 körül tüntetést írt, de nem tette közzé. 1741-ben, 1750-ben és 1761-ben Euler kettőt tett közzé, amelyek megismétlődtek és a binomiális fejlõdést alkalmazták , és egyet, amely a maradék eloszlását vizsgálja a figyelembe vett prím számra modulo. Az egyik 1801-ben találja meg a Gauss Disquisitiones Arithmeticae-ban . Összefoglalja ott az Euler első bemutatóját is, és a multinomális fejlesztése segítségével gyorsabb verziót ad .

Gauss 1801-ben megemlíti, hogy "Ezt a figyelemre méltó tételt, éppúgy eleganciája, mint nagy hasznossága miatt, Fermat-tételnek szokták nevezni , a feltaláló neve után". A Fermat kis tételének ( kleine Fermatsche Satz ) nevét Kurt Hensel 1913-ból származó munkájában találjuk .

Egy fiatal amerikai hallgató , akit többek között Dickson idézett, azzal érvelt, hogy a tétel már 2000 évvel a Fermat előtt Kínában is ismert volt, a konkrét esetben az a = 2, kölcsönös - triviálisan hamis - kíséretében. Ez a "  kínai hipotézis  (be)  " csak városi legenda , egy fordítási hiba miatt, amely felerősítette és torzította az idézeteket .

Példák

Íme néhány példa (a második állítás alapján):

Alkalmazások

Az alkalmazások számosak, különösen a kriptográfia területén . Vannak azonban klasszikus példák a tétel alkalmazására a tiszta matematikában .

Elméleti alkalmazások

Fermat kis tételét történelmileg bizonyos egész számok prímtényezőinek termékbontásának elemzésére használják . Így írt Fermat Mersenne-nek ( 1588 - 1648 )  : „Kérdezi tőlem, hogy a 100 895 598 169 szám elsődleges-e vagy sem, és egy módszer a felfedezésre egy nap alatt, ha elsődleges vagy összetett . Erre a kérdésre azt válaszolom, hogy ez a szám ennek a kettőnek a 898 423 és 112 303 szorzatából áll, amelyek elsődlegesek. Euler analóg módszerrel érvényteleníti Fermat egyedi hamis sejtéseit, bizonyítva, hogy a Fermat-számok nem mind prímértékek.

Ezt a tételt alkalmazzák az algebrai számelmélet eredményeinek bemutatására is , például a Herbrand-Ribet tételre . Ez túlmutat a szigorú kereteken számtani , a felhasználás a tanulmány a fix pont a endomorphism Frobenius például.

Aszimmetrikus rejtjelezés

A nyilvános kulcsú rejtjelezés olyan kódnak felel meg, amely két titkosítási kulcs segítségével igyekszik biztosítani az üzenetek bizalmasságát . Az egyik, amely lehetővé teszi az üzenet titkosítását , nyilvános. A másikat a visszafejtés céljával titokban tartják.

Az aszimmetrikus rendszerek fontos családja az RSA titkosítás algoritmusát használja . A titkos kulcs egy nagy egész szám bontása, gyakran több száz számjegy. Két fő tényezőt tartalmaz . A XXI .  Század elején az ipari technikák többsége a kis Fermat-tételen alapult, hogy nagy prímszámokat generáljon, vagy tesztelje a szám prímaságát.

Primalitás teszt

Fermat kis tétele szükséges feltételt ad ahhoz, hogy a p szám elsődleges legyen. Valóban, minden egy kisebb p , a p - 1 kell lennie egybevágó 1 modulo p . Ez az elv képezi a Fermat primalitási teszt alapját . Ennek a tesztnek számos algoritmikus variációja van. A legismertebbek a Solovay-Strassen prímteszt és különösen a Miller-Rabin prímteszt .

Ál-prímszám

Az előző tesztek szükséges, de nem elegendő feltételt alkalmaznak. Tehát léteznek nem elsődleges egészek p úgy, hogy minden olyan prím p , a p - 1 mindig egybevágó 1 modulo p . Az 1 729 szám egy példa. Az ilyen p egész számokat Carmichael-számoknak nevezzük .

Az előző bekezdésben feltüntetett tesztek mind statisztikai jellegűek, abban az értelemben, hogy mindig fennáll annak a valószínűsége, néha nagyon alacsony, hogy a tesztet sikeresen teljesítő szám mégsem az első. Ezeket a számokat álprimeknek nevezzük, és bizonyos tesztekhez kötik.

Tüntetések

Lagrange-tétel szerint

Euler második bizonyíték az első állítás, amint felvesszük Gauss, újrafogalmazott modern értelemben áll bizonyítania, hogy a rend t az egy a multiplikatív csoportjában (ℤ / p ℤ) * osztója a rend p - 1 e csoport (ez tehát azt bizonyítja, Lagrange-tétel az adott esetben az alcsoport generált által a ). Azonnal levezeti Fermat kis tételét, az a t ≡ 1 (mod p ) egyenlet két tagjának a hatványra emelésével : az egész ( p - 1) / t értékre . Az eredmény és annak bizonyítása bármely véges csoportra érvényes (itt a p - 1 sorrendű multiplikatív csoport (ℤ / p ℤ) * ).

Euler és Leibniz bemutatója

Euler és Leibniz bizonyítja a második kijelentés használja Newton binomiális képlet és érvelés indukcióval az egész egy , feltételezték, hogy pozitív az általánosság elvesztése nélkül . Indoklásuk (amelyet itt a Gauss később bevezetett kongruenciák nyelvén fogalmaztak meg) a következő:

Ehhez elegendő kifejleszteni a ( k + 1) p kifejezést, és észrevenni, hogy az összes binomiális együttható az első és az utolsó kivételével p többszöröse, mert p elsődleges. A bizonyítást a „Binomiális együttható” cikk „Binomiális osztók és együtthatók” szakasza adja .

A két állítás egyenértékűsége

Ha az első állítás igaz, akkor a második is: a p - egy egyenlő a termék egy ( a p -1 - 1), ezért mindig osztható p , mert ha az első tényező, a , nem, majd a második van.

Ezzel szemben, az első állítás levezethető a második segítségével Eukleidész lemma  : ha egy ( a p -1 - 1) osztható p , és ha a nem, akkor egy p -1 - 1.

Elemi számtani bizonyítás

Az első állítás másik bizonyítéka analóg (egyszerűbb fogalmakkal) Gauss lemmájának bizonyításával  : itt az a trükk, hogy a modulo p értékét kétféle módon értékeljük

.

A bizonyítás rendkívül gyorsan végez számításokat a gyűrű ℤ / p ℤ , de mi is részletesen használatával csak maradékos osztás , euklideszi lemma , és algebrai tulajdonság kongruencia egészeken .

Demonstráció

Tegyük fel, hogy a nem osztható p- vel, és jelölje

N a termék a .2 a .3 a .…. ( P - 1) a R k a fennmaradó euklideszi megosztása ka által p , bármely egész szám k 1 és p - 1. Ekkor no r k nulla, mert (Euclid lemma szerint) no ka osztható p-vel  ; az r k kettőnként különböznek egymástól, mert ha r i = r j, akkor ( i - j ) a osztható p-vel , tehát (ismét Euclid-féle lemmával) i - j is, tehát (például - p < i - j < p ) i = j .

Bemutató kettős számlálással

Fermat kis tételét be lehet mutatni, ha két különböző módon számoljuk meg a p- szimbólum szavak számát egy a- szimbólum ábécében , legalább két különböző szimbólummal.

Általánosítások

Egy enyhe általánosítása a tételnek a következő: ha p prímszám, és ha m és n jelentése szigorúan pozitív egész szám úgy, hogy m ≡ n mod ( p - 1), akkor, bármely egész szám egy  :

.

Valóban, p modulo , a két tag 0-ra egyezik, ha a osztható p-vel , és ha nem, akkor a n - m = ( a p - 1 ) ( n - m ) / ( p - 1) ≡ 1 ( n - m ) / ( p - 1) = 1. Ebben a formában a tétel megalapozza az RSA titkosítási algoritmust .

Kis Fermat-tétel általánossá az Euler-tétel  : minden nem nulla természetes egész szám n , és minden egész egy prím n , van

ahol jelöli a Euler mutatószám az N , egyenlő a sorrendben a csoport egységek a gyűrű ℤ / n ℤ . Ha n prímszám, akkor φ ( n ) = n - 1 és megtaláljuk Fermat kis tételét.

Ugyanígy általánosít minden véges mezőre, tehát a számmező egész számainak gyűrűjének egy hányadosa egy főideál által .

Megjegyzések és hivatkozások

  1. Bőrgyár és Henry 1894 , p.  209., Fermat levele Frénicle-hez 1640. október 18-án, 1. jegyzet.
  2. Fermat 1679 , p.  163; Fermat műveinek egymást követő publikációit a Tannery és Henry 1891 előzetes figyelmeztetésében tanulmányozzuk , lásd még a konkordancia táblázatát p.  440 .
  3. Bőrgyár és Henry 1894 , p.  209., Fermat levele Frénicle-hez 1640. október 18-án.
  4. M. Bülher és A. Pichel-Pajus, Fermat tételének bemutatása Leibniz által , Mnemosyne n ° 19, Bonnes vieux pages (2), 2007, p.  61-66 .
  5. (La) L. Euler, "  Theorematum quorundam ad numeros primos spectantium demonstratio ( E054 )  " , megjegyzés. Acad. Sci. Petrop. , vol.  8,1741, P.  141–146 ( online olvasás ), írták és bemutatták 1736-ban.
  6. (La) L. Euler, "  Theoremata circa divisores numerorum ( E134 )  " , Novi Comment. Acad. Sci. Petrop. , vol.  1,1750, P.  20–48 ( online olvasás ), írták és bemutatták 1747-ben.
  7. (La) L. Euler, „  Theoremata circa residua ex Divisione potestatum relicta ( E262 )  ” , Novi Comment. Acad. Sci. Manó. Petrop. , vol.  7,1761, P.  49–82 ( online olvasás ), 1755-ben írták és 1758-ban mutatták be ( Poullet Delisle fordításban , a megadott hivatkozás ( n o  50): "Comm. November Petrop. T. VIII., 70. o." , De az eredeti 1801- ben Gauss ezt írta: "T. VII ” ).
  8. C. F. Gauss (  latin fordítással A.-C.-M. Poullet-Delisle), Aritmetikai kutatás [“  Disquisitiones arithmeticae  ”], Courcier,1807( 1 st  ed. 1801), p.  32-34, 49. o.
  9. Gauss 1807 , n ° 50.
  10. Gauss 1807 , 51. sz.
  11. Hensel ezen a néven ad egy általánosított állítást egy véges kommutatív csoportnak, (de) Kurt Hensel , Zahlentheorie , Göschen, Berlin / Lipcse, 1913, digitalizálva a Gutenberg projekten , V.6. §, 128. o. A Gutenberg projekt változatával. .
  12. (in) JH Jeans , "Fermat tételének fordítottja", Messenger of Mathematics  (in) , vol. 1898, 27. o.  174 .
  13. (in) Leonard Eugene Dickson , History of the Theory of Numbers  (hu) [ részletek kiadásban ], 1919, vol. 1: Oszthatóság és elsődlegesség, p.  59 .
  14. Lásd az OEIS A230579 jelű megjegyzéseit .
  15. (in) J. Needham (szerk.), Matematika és az ég és föld tudományai, tudomány és civilizáció Kínában, vol. 3, CUP , 1959, c. 19. o.  54. , d. Megjegyzés, előnézet a Google Könyvekben .
  16. (in) Paulo Ribenboim , The New Book of Records prímszám ( olvas online ) , p.  103-105.
  17. P. de Fermat, levél Marin Mersenne az április 7, 1643 olvasás .
  18. Lásd például (in): Sanjoy Dasgupta, Christos Papadimitriou és Umesh Vazirani , algoritmusok , McGraw-Hill ,2008, P.  23-25 , vagy ez a helyesbített gyakorlat a "Bevezetés a számelméletbe" leckéből a Wikegyetemről .

Bibliográfia

Matematika

Matematikatörténet

Lásd is

Kapcsolódó cikk

Fermat hányadosa  (in)

Külső linkek

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">