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 .
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 .
Íme néhány példa (a második állítás alapján):
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 .
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.
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.
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 .
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.
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 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ő:
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.
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. EkkorFermat 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.
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 .
Fermat hányadosa (in)