Fermat kis tétele

A Fermat-féle kis tétel egy számelméleti tétel, amely kimondja, hogy [1] :

Ha egy prímszám , és egész szám , amivel nem osztható, osztható vele $p$ $a$ $p,$ $a^{p-1}-1$ $p.$

A kongruenciák elméletének nyelvén : 1 modulo a prímhez kongruens . Formális jelölés: $a^{p-1}$ $p$ $a^{p-1}\equiv 1{\pmod {p}}$

Például ha akkor és $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

A Fermat-féle kis tétel az Euler-tétel [2] speciális esete, amely viszont a Carmichael - tétel és a Lagrange-féle csoporttétel speciális esete véges ciklikus csoportokra . A tételt Pierre Fermat bizonyítás nélkül fogalmazta meg , az első bizonyítást Leonhard Euler és Gottfried Wilhelm Leibniz adta .

A Fermat-féle kis tétel nemcsak az egész számok elméletében, hanem tágabb területeken is a kutatás egyik fő tételévé vált [3] [4] .

Történelem

Pierre Fermat a tétel eredeti megállapítását Bernard Frenicle francia matematikushoz írt 1640 -es levelében fogalmazta meg [5] :

Minden prímszám ekvivalens [eredeti: mértékek ] egy hatvány mínusz egy tetszőleges bázissal és egy kitevője egyenlő az adott prímszámmal mínusz egy… És ez az állítás általában minden bázisra és minden prímre igaz. Elküldeném a bizonyítékot, ha nem lenne olyan hosszú.

Eredeti szöveg (fr.)[ showelrejt] Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné −1… Et cette javaslat est généralement vraie en toutes toutes nombres ; de quoi je vous envoierois la demonstration, si je n'appréhendois d'être trop long. — Forrás: Fermat a Frenicle

Példaként Fermat megadja a 3, 9, 27, 81, 243, 729… és a 13 prímszámot. A 13 osztja a 27 − 1-et (a 27 kitevője 3, a 3 pedig osztja a 13 − 1-et), ami azt jelenti, hogy A 13 osztja a 729 − 1-et is (729 kitevője 6, és 3 többszöröse).

Fermat maga is bizonyítás nélkül hagyta tételét. Az első matematikus, aki bizonyítékot talált, Gottfried Wilhelm Leibniz volt, akinek kéziratai szerint 1683 előtt ismerte a bizonyítékot. Leibniz nem tudott Fermat eredményéről, és önállóan fedezte fel a tételt [6] . Leibniz munkáját azonban nem publikálták, a bizonyítékot Euler publikálta 1736-ban a Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio-ban [7] . 1806-ban James Ivory skót matematikus egy olyan bizonyítást publikált, amely azon alapul, hogy ha a maradékok modulo teljes rendszerén végigfut , akkor minden nem többszörös termék esetében a maradékok modulo teljes rendszerén is ez az elképzelés a modern bizonyítások alapja. [8] . $x$ $p$ $a,$ $p,$ $fejsze$ $p;$

A számot Fermat privát számának hívják . D. A. Grave orosz matematikus azt javasolta, hogy a Fermat-hányados sohasem osztható 1000-et nem meghaladó prímszámokra, ez igaz, de hamarosan kiderült egy ellenpélda: Fermat hányadosa ugyanis osztható 1093-mal [9] . ${\frac {a^{p-1}-1}{p))$ $p.$ $p=1093,a=2$

Alternatív megfogalmazás

A következő megfogalmazást az a követelmény különbözteti meg, hogy a szám nem osztható a következővel: $a$ $p$

Ha egy prímszám , és tetszőleges egész szám , akkor összehasonlítható a modulo -val , azaz . $p$ $a$ $a^{p}$ $a$ $p$ $a^{p}\equiv a{\pmod {p}}$

Például ha , akkor és . $a=7;p=5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

Könnyen kimutatható, hogy ez a megfogalmazás az eredetire redukálódik. Tehát, ha osztható -vel , akkor és , azaz. . Ha nem osztható -vel , akkor a kifejezés ekvivalens a [2] kifejezéssel . $a$ $p$ $a\equiv 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $a$ $p$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Mind az elsődleges, mind az alternatív megfogalmazás használható annak tesztelésére, hogy egy adott szám prímszám-e (lásd alább ), de az elsődleges megfogalmazás robusztusabb abban az értelemben, hogy több összetett számot is elutasít . Példa: Ellenőrizzük, hogy prímszám-e. Legyen B egy alternatív megfogalmazásban , és ez összevethető 4 mod 6-tal. Vagyis a 6-os számot nem utasítják el, egyszerűségét nem cáfolják. Ha visszatérünk az eredeti tételhez: , akkor , és ez nem hasonlítható össze 1 mod 6-tal, ahogy annak lennie kellene, ha p prímszám. Tehát az alapformuláció hatékonyabb az összetett számok kivágásában. $6$ $a=4.$ $4^{6}=4096=682\szer 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\szer 6+4$

Bizonyíték

A Leibniz által javasolt tétel bizonyítása

Tekintsünk egy p fokú homogén polinomot n változóval :

S(x,y,z,\pontok ,w)=(x+y+z+\pontok +w)^{p}-(x^{p}+y^{p}+z^{p}+\ pont+w^{p}).

A zárójeleket kinyitva megkapjuk a monomiális együtthatót (ahol a hatványok közül legalább kettő nem egyenlő nullával, és az összes hatvány összege egyenlő p ) multinomiális együtthatónak nevezzük , és a képlettel számítjuk ki. $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alpha ,\beta ,\gamma \ldots \nu$

M={\frac {p!}{\alpha !\beta !\gamma !\dots \nu !}}).

Mivel a hatványok ennél kisebbek , a multinomiális együttható nevezője nem tartalmaz olyan tényezőket, amelyek érvényteleníthetnének, így a polinom összes együtthatója többszöröse , így a következő azonosság igaz: $\alpha ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $p.$

(x+y+z+\pontok +w)^{p}-(x^{p}+y^{p}+z^{p}+\pontok +w^{p})=pH(x,y ,z,\pontok ,w),

ahol egy pozitív egész együtthatójú polinom. $H(x,y,z,...,w)$

Legyen most ebben az azonosságban (itt n a változók száma az eredeti polinomiális kifejezésben), ezért többszöröse . Ha nem osztható prímszámmal, akkor [10] osztható vele . $x=y=...=w=1,H(1,1,1,...,1)=N,$ $n^{p}-n=Np$ $n(n^{p-1}-1)$ $p$ $n$ $p,$ $n^{{p-1}}-1$

Bizonyítás indukcióval

Bizonyítsuk be, hogy tetszőleges p prímszám és a nemnegatív egész szám esetén a p − a osztható p -vel . Indukcióval bizonyítjuk egy . _

Bázis. Ha a = 0 , a p − a = 0 , és osztható p -vel .

Átmenet. Legyen igaz az állítás a = k -re . Bizonyítsuk be a = k + 1 -re .

a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \choose l}k^{l}-k-1=k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \válasszon l}

De k p − k osztható p -vel az indukciós hipotézis alapján. A többi kifejezés tartalmazza a faktort . Mert ennek a törtnek a számlálója osztható p -vel, a nevezője pedig p -re való másodpím , ezért osztható p -vel . Mivel minden egyes tag osztható p -vel , a teljes összeg is osztható p -vel . ${p \choose l}={p! \over l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \válasszon l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \válasszon l}$

Negatív a és páratlan p esetén a tétel könnyen igazolható b = − a helyettesítésével . Negatív a és p = 2 esetén a tétel igazsága abból következik, hogy a 2 − a = a ( a − 1) [11] .

Bizonyítás csoportelmélet segítségével

A Fermat-féle kis tétel egyik legegyszerűbb bizonyítása a csoportelméletből származó Lagrange-tétel egy következményén alapul , amely szerint egy véges csoport elemeinek sorrendje felosztja a csoport sorrendjét.

Emlékezzünk vissza, hogy egy véges csoport sorrendje elemeinek száma, egy elem sorrendje pedig fokának legkisebb természetes kitevője, amely egyenlő a csoport egységelemével . $G$ $g\in G$ $e$ $G$

Legyen a sorrend véges csoportja . Mivel az elemsorrend osztódik , ebből következik, hogy . $G$ $n$ $g\in G$ $n$ $g^{n}=e$

Tekintsük a maradékok mezőjét modulo . Egy egész szám levonását jelöli . A mező nullától eltérő elemei a szorzás szempontjából egy csoportot alkotnak. $\mathbb {Z} _{p}$ $p$ $a$ $a$ $\mathbb {Z} _{p}$

Ennek a csoportnak a sorrendje nyilvánvalóan . Egyetlen eleme a . Ebből következik, hogy minden olyan szám esetében, amely nem osztható -vel , de ez csak összehasonlítást jelent [1] $p-1$ $egy$ $a$ $p$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Bizonyítás moduláris aritmetikával

Lemma. Bármilyen prímszám és olyan egész szám esetén, amely nem többszöröse , a szám és a számok szorzata , ha elosztjuk a maradékkal, ugyanazokat a számokat adják , esetleg más sorrendben írva. $p$ $k$ $p$ $k$ $1,2,3,\ldots ,p-1$ $p$ $1,2,3,\ldots ,p-1,$

A lemma bizonyítéka

A szorzat és egyik szám sem többszöröse , ezért a maradék nem lehet . Minden maradvány más. Bizonyítsuk be az utolsó állítást ellentmondással. Legyen at és két szorzat, és adjuk meg, ha azonos maradékokkal osztjuk , akkor a különbség többszöröse , ami lehetetlen, mivel nem többszöröse . Összességében különböző nem nulla maradékok vannak a -val való osztásból . $k$ $1,2,3,\ldots ,p-1$ $p$ $0$ $a,b\in \{1,2,3,\ldots ,p-1\}$ $a\neq b$ $ak$ $bk$ $p$ $ak-bk=(ab)k$ $p$ $ab$ $p$ $p-1$ $p$

Mivel a fenti lemma szerint az a , 2 a , 3 a , ..., ( p − 1) a számok elosztása utáni maradékok az 1, 2, 3, ... számok permutációjáig , p − 1 , akkor . Innen . Az utolsó reláció redukálható ( p − 1)-re! , mivel minden tényező p bázisú koprímszám , így megkapjuk a szükséges állítást [12] . $a\cdot 2a\cdot 3a\ldots (p-1)a\equiv 1\cdot 2\cdot 3\ldots (p-1){\pmod {p))$ $a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p))$ $a^{p-1}\equiv 1{\pmod {p}}$

Következmények és általánosítások

Ha prímszám, akkor a [13] egyenlőség igaz a mezőben . $p$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Ha egy prímszám nem 2 és 5, akkor az a szám, amelynek decimális jelölése csak számjegyeket tartalmaz , osztható -vel . Ebből következik, hogy minden olyan egész számra , amely nem osztható sem 2-vel, sem 5-tel, felvehet egy olyan számot, amely csak kilencből áll, és osztható -vel . Ezt a tényt az oszthatósági jelek és a periodikus törtek elmélete használja [14] . $p$ $10^{p-1}-1$ $9$ $p$ $N$ $N$
A Fermat-féle kis tétel lehetővé teszi számok prímosztóinak megtalálását a [ 15] alakban . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
Fermat kis tételének általánosítása az algebrai számokra Schönemann 1839-ben megfogalmazott tétele : legyen egy d fokú normalizált polinom gyöke, p pedig egy prímszám. Aztán [16] . $a_{1},\pontok ,a_{d}$ $f\in \mathbb {Z} [x]$ $a_{1}^{p}+a_{2}^{p}+\pontok +a_{d}^{p}\equiv a_{1}+\dots +a_{d}{\pmod {p))$
Fermat kis tétele magába foglalja Wilson tételét : Egy természetes szám akkor és csak akkor prím , ha osztható p -vel . $p>1$ $(p-1)!+1$

Wilson-tétel bizonyítása

A Lagrange-tétel a számelméletben kimondja, hogy ha egy fokszámú polinom osztható egy prímszámmal a változó több mint összehasonlíthatatlan modulo (azaz eltérő maradványai vannak, ha elosztjuk -vel ) értéke esetén , akkor osztható -val bármely értéknél . $n$ $p$ $n$ $p$ $p$ $x$ $p$ $x$

Tekintsük a polinomot

G(x)=(x-1)(x-2)(x-3)...(x-(p-1))-(x^{p-1}-1),

hol van egy prímszám.

p

Akkor találjuk:

G(1)=0,G(2)=1-2^{p-1},G(3)=1-3^{p-1},...,G(p-1)=1- (p-1)^{p-1}.

Fermat kis tétele értelmében ezek a számok oszthatók egy prímszámmal , így az összehasonlításnak inkongruens megoldásai vannak . Másrészt a polinom foka csak ebből adódik, amiből az következik, hogy a polinom osztható minden értékre és különösen $p$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $p$ $x,$ $x=0.$

Eszközök $G(0)=[(p-1)!+1]\equiv 0{\pmod {p}}.$

És ha ezen felül bebizonyítjuk, hogy minden nem egyszerű természetesre , kivéve , akkor megkapjuk a tétel bizonyítását. [17] $n$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Alkalmazások

Fermat pszeudoprímek és primalitásteszt

A Fermat-féle kis tétel segítségével ellenőrizhető, hogy egy szám prím-e: ha nem osztható -vel , akkor összetett számról van szó . A Fermat-féle kis tétel megfordítása azonban általában hibás: ha a és másodprím számok , és oszthatók -vel , akkor a szám lehet prím és összetett is. Abban az esetben, ha összetett, azt Fermat -féle pszeudoegyszerűnek nevezzük az alaphoz . $(a^{p}-a)$ $p$ $p$ $a$ $p$ $a^{p-1} - 1$ $p$ $p$ $p$ $a$

Például a kínai hipotézis azt állítja, hogy akkor és csak akkor prímszám, ha [18] . Itt van egy közvetlen kijelentés, hogy ha prím, akkor , Fermat kis tételének speciális esete. Az a fordított állítás, hogy ha , akkor egyszerű, a Fermat-féle kis tétel megfordításának speciális esete. Ez az átalakítás hamis: Sarrus 1820-ban megállapította, hogy egy szám osztható -val, mert osztható -vel . Ez azonban egy összetett szám : . Így egy pszeudoprím szám a 2. bázisban [19] . $p$ $2^{p}\equiv 2{\pmod {p}}$ $p$ $2^{p}\equiv 2{\pmod {p}}$ $2^{p}\equiv 2{\pmod {p}}$ $p$ $N=2^{341-1}-1$ $341$ $N$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

Általános esetben a Fermat-féle kis tétel inverze is kudarcot vall. Ellenpélda általános esetben a Carmichael-számok : ezek olyan számok , amelyek pszeudoprím alapszámúak az összes -hoz tartozó másodprímhez . Carmichael legkisebb száma az 561. $p$ $a$ $a$ $p$

Mivel Fermat kis tételének megfordítása hibás, feltételének teljesülése nem garantálja, hogy prímszámról van szó . Ennek ellenére Fermat kis tétele támasztja alá a Fermat-tesztet az elsődlegességre [20] . A Fermat-próba egy valószínűségi primalitásteszt: ha a tétel nem igaz, akkor a szám pontosan összetett, ha pedig igen, akkor a szám bizonyos valószínűséggel prím . Más valószínűségi módszerek mellett megjegyezhető: a Solovay-Strassen-próba és a Miller-Rabin-próba , utóbbi bizonyos mértékig Fermat kis tételére támaszkodik [21] . Van egy determinisztikus algoritmus is: Agrawal-Kayala-Saksen teszt . $p$

Ezenkívül igaz a következő két állítás. Ha egy pár kielégíti az összehasonlítást , akkor a számpár is kielégíti azt. Bármilyen prímszámra és minden olyanra , ahol , az érték Fermat pszeudoprím az alaphoz képest [22] . $(2,n)$ $a^{n-1}\equiv 1{\pmod {n}}$ $(2,2^{n}-1)$ $n$ $a>2$ $(a^{2}-1,n)=1$ ${\frac {a^{2n}-1}{a^{2}-1}}$ $a$

RSA algoritmus

A Fermat-féle kis tételt az RSA titkosítási algoritmus helyességének bizonyítására is használják [2] .

Lásd még

Jegyzetek

↑ 1 2 Vinberg, 2008 , p. 43.
↑ 1 2 3 Sagalovich, 2014 , p. 34.
↑ Elementary Mathematics enciklopédiája, 1. könyv, Aritmetika, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961.- 280. o.
↑ Z. I. Borevics, I. R. Safarevics. Számelmélet. — M .: Nauka, 1972. — 175 p.
↑ Gracian E. Prímszámok . Hosszú út a végtelenbe. - De Agostini, 2014. - T. 3. - S. 45. - 148 p. — (Matematika világa). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Számok – a tudomány nyelve, 2008 , p. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Number Theory Through Inquiry Archiválva : 2012. szeptember 16. a Wayback Machine -nél . - 2006. - pp. 62-63.
↑ John J. O'Connor és Edmund F. Robertson . Sir James Ivory egy életrajz a MacTutor archívumában .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Egy matematika tankönyv lapjai mögött: Számtan. Algebra. Geometria . - M . : Oktatás, 1996. - S. 30 . — 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Számok – a tudomány nyelve, 2008 , p. 231-234.
↑ Vinberg, 2008 , p. 44.
↑ QUANTUM, 2000, 1. sz., Senderov V, Spivak A. Fermat kis tétele.
↑ Akritas A. A számítógépes algebra alapjai alkalmazásokkal, 83. o.
↑ Danzig, T. Számok – a tudomány nyelve, 2008 , p. 232-234.
↑ QUANTUM, 2000, 3. sz., Senderov V, Spivak A Fermat kis tétele
↑ Vinberg, 2008 , p. 49.
↑ Danzig, T. A számok a tudomány nyelve, 2008 , p. 234-238.
↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103-105, ISBN 0-387-94457-5 .
↑ Weisstein EW Fermat Pseudoprime .. - 2005 ..
↑ Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Információbiztonság: tankönyv. - M.: MIPT, 2011. - S. 236-237. — 262 p. Val vel. — ISBN 978-5-7417-0377-9 .
↑ Williams HC Primality tesztelése számítógépen // Ars Combin. - 1978. - 1. évf. T. 5 , sz. Nem. 12 . — P. 127-185 .
↑ Shitov Yu. A. Numerikus módszerek a kriptográfiában.

Irodalom

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Az elemi matematika enciklopédiája. I. kötet: Számtan. – 1951.
Borevich Z. I., Shafarevich I. R. Számelmélet . — M .: Nauka, 1972. — 510 p. Archiválva : 2011. január 8. a Wayback Machine -nél
Vinberg EB Fermat kis tétele és általánosításai // Matem. felvilágosodás - M . : MTSNMO Kiadó , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Fermat kis tétele" . - Kvant , 1972. - 10. sz . (nem elérhető link)
Danzig, T. A számok a tudomány nyelve . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Neszterenko Yu. V. A számelmélet algoritmikus problémái . - 1997. - Kiadás. 2. szám , harmadik sorozat .
Sagalovich Yu. L. Bevezetés az algebrai kódokba - 3. kiadás, átdolgozva. és további - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Fermat kis tétele // Kvant. - 2000. - 1. sz .
Senderov V, Spivak A. Fermat kis tétele // Kvant. - 2000. - 3. sz .