Fermatova malá věta

Fermatova malá věta je věta v teorii čísel , která říká, že [1] :

Jestliže je prvočíslo a je celé číslo , které není do té doby dělitelné, je dělitelné číslem $p$ $A$ $p,$ $a^{p-1}-1$ $p.$

V jazyce teorie kongruencí : shoda s 1 modulo a prvočíslo . Formální zápis: $a^{p-1}$ $p$ $a^{p-1}\ekviv 1{\pmod {p}}$

Například pokud tehdy a $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cdot 9.$

Fermatova Malá věta je speciálním případem Eulerovy věty [2] , která je zase speciálním případem Carmichaelovy věty a Lagrangeovy věty o grupách pro konečné cyklické grupy . Větu bez důkazu vyslovil Pierre Fermat , první důkaz podali Leonhard Euler a Gottfried Wilhelm Leibniz .

Fermatova malá věta se stala jednou z hlavních teorémů pro výzkum nejen v teorii celých čísel, ale i v širších oblastech [3] [4] .

Historie

Pierre Fermat formuloval původní tvrzení teorému v dopise z roku 1640 francouzskému matematikovi Bernardu Frenicleovi [5] :

Každé prvočíslo je ekvivalentní [originál: míry ] mocnina mínus jedna s libovolným základem a exponentem rovným danému prvočíslu mínus jedna... A toto tvrzení obecně platí pro všechny základy a všechna prvočísla. Kdyby to nebylo tak dlouho, poslal bych ti důkaz.

Původní text (fr.)[ zobrazitskrýt] Tout nombre premier mesur 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 proposition est premier genéralement vraie en toutes progress et en toutes ; de quoi je vous envoierois la demonstrace, si je n'appréhendois d'être trop long. — Zdroj: Fermat a Frenicle

Fermat uvádí jako příklad průběh 3, 9, 27, 81, 243, 729… a prvočíslo 13. 13 dělí 27 − 1 (exponent 27 je 3 a 3 dělí 13 − 1), což znamená, že 13 také dělí 729 − 1 (exponent pro 729 je 6 a je násobkem 3).

Fermat sám opustil svou větu bez důkazu. Prvním matematikem, který našel důkaz, byl Gottfried Wilhelm Leibniz, jehož rukopisy naznačují, že znal důkaz již před rokem 1683. Leibniz o Fermatově výsledku nevěděl a teorém objevil nezávisle [6] . Leibnizova práce však nebyla publikována a důkaz publikoval Euler v roce 1736 v Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio [7] . V roce 1806 skotský matematik James Ivory publikoval důkaz založený na skutečnosti, že pokud prochází celým systémem reziduí modulo , pak pro jakýkoli nenásobný součin také prochází úplným systémem reziduí modulo , je tato myšlenka základem moderních důkazů. [8] . $X$ $p$ $A,$ $p,$ $sekera$ $p;$

Číslo se nazývá Fermatovo soukromé . Ruský matematik D. A. Grave navrhl, že Fermatův kvocient není nikdy dělitelný U prvočísel nepřesahujících 1000 je to pravda, ale brzy byl objeven protipříklad: Fermatův kvocient je dělitelný 1093 [9] . ${\frac {a^{p-1}-1}{p))$ $p.$ $p=1093,a=2$

Alternativní znění

Následující formulace se vyznačuje tím, že neexistuje požadavek, aby číslo nebylo dělitelné : $A$ $p$

Jestliže je prvočíslo a je libovolné celé číslo , pak je srovnatelné s modulo , tedy . $p$ $A$ $a^{p}$ $A$ $p$ $a^{p}\equiv a{\pmod {p}}$

Například pokud , pak a . $a = 7; p = 5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cdot 1+2.$

Je snadné ukázat, že tato formulace je redukována na původní. Pokud je tedy dělitelné , pak a , tj. . Pokud není dělitelný , pak je výraz ekvivalentní výrazu [2] . $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}\ekviv 1{\pmod {p}}$

Primární i alternativní formulace mohou být použity k testování, zda je dané číslo prvočíslo (viz níže ), ale primární formulace je robustnější v tom smyslu, že odmítá více složených čísel . Příklad: Zkontrolujeme, zda se jedná o prvočíslo. Nechť B získáme v alternativní formulaci , a to je srovnatelné se 4 mod 6. To znamená, že číslo 6 není odmítnuto, jeho jednoduchost není vyvrácena. Pokud se vrátíme k původní větě: , pak , a to není srovnatelné s 1 mod 6, jak by mělo být, když p je prvočíslo. Základní formulace je tedy efektivnější při získávání složených čísel. $6$ $a=4.$ $4^{6}=4096=682\times 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\times 6+4$

Důkazy

Důkaz věty navržené Leibnizem

Uvažujme homogenní polynom stupně p s n proměnnými:

S(x,y,z,\tečky ,w)=(x+y+z+\tečky +w)^{p}-(x^{p}+y^{p}+z^{p}+\ tečky+w^{p}).

Otevřením závorek dostaneme koeficient u monomiálu (kde alespoň dvě z mocnin se nerovnají nule a součet všech mocnin je roven p ) se nazývá multinomický koeficient a vypočítá se podle vzorce $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alpha ,\beta ,\gamma \ldots \nu$

M={\frac {p!}{\alpha !\beta !\gamma !\tečky \nu !}}).

Vzhledem k tomu, že mocniny jsou menší , jmenovatel multinomického koeficientu neobsahuje faktory, které by se mohly rušit, a proto jsou všechny koeficienty polynomu násobky . Platí tedy následující identita: $\alpha ,\beta ,\gamma ...$ $p,$ $p,$ $S$ $p.$

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

kde je polynom s kladnými celočíselnými koeficienty. $H(x,y,z,...,w)$

Nechť nyní v této identitě (zde n je počet proměnných v původním polynomickém výrazu), tedy je násobek . Pokud není dělitelná prvočíslem, pak [10] je dělitelná právě jím . $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$

Důkaz indukcí

Dokažme, že pro libovolné prvočíslo p a nezáporné celé číslo a je a p − a dělitelné p . Dokazujeme indukcí na . _

Základna. Pro a = 0 je a p − a = 0 a je dělitelné p .

Přechod. Nechť tvrzení platí pro a = k . Dokažme to pro a = k + 1 .

a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\součet _{l=1}^{p-1}{p \vyberte l}k^{l}-k-1=k^{p}-k+\součet _{l=1}^{p-1}k^{l}{p \vyberte l}

Ale k p − k je dělitelné p indukční hypotézou. Zbytek termínů obsahuje faktor . Neboť , čitatel tohoto zlomku je dělitelný p , a jmenovatel je coprime k p , proto je dělitelný p . Protože všechny jednotlivé členy jsou dělitelné p , je i celý součet dělitelný p . ${p \vyberte l}={p! \over l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \vyberte l}$ $k^{p}-k+\součet _{l=1}^{p-1}k^{l}{p \vyberte l}$

Pro záporné a a liché p lze větu snadno dokázat dosazením b = − a . Pro záporné a a p = 2 pravdivost věty vyplývá z a 2 − a = a ( a − 1) [11] .

Důkaz pomocí teorie grup

Jeden z nejjednodušších důkazů Fermatovy malé věty je založen na důsledku Lagrangeovy věty z teorie grup , který říká, že pořadí prvku konečné grupy rozděluje pořadí grupy.

Připomeňme, že řád konečné grupy je počet jejích prvků a řád prvku je nejmenší přirozený exponent jeho stupně rovný jednotkovému prvku grupy . $G$ $g\in G$ $E$ $G$

Dovolit být konečná skupina řádu . Protože se pořadí prvků dělí , vyplývá z toho, že . $G$ $n$ $g\in G$ $n$ $g^{n}=e$

Uvažujme pole reziduí modulo . Odečtení celého čísla bude označeno . Nenulové prvky pole tvoří skupinu s ohledem na násobení. $\mathbb {Z} _{p}$ $p$ $A$ $A$ $\mathbb {Z} _{p}$

Pořadí této skupiny je zjevně . Jeho jediným prvkem je . Z toho vyplývá, že pro každé číslo , které není dělitelné , , to ale znamená pouze srovnání [1] $p-1$ $jeden$ $A$ $p$ $a^{{p-1}}=1$ $a^{p-1}\ekviv 1{\pmod {p}}$

Důkaz pomocí modulární aritmetiky

Lemma. Pro jakékoli prvočíslo a celé číslo , které není násobkem , dávají součin a čísla při dělení zbytkem stejná čísla , možná zapsaná v nějakém jiném pořadí. $p$ $k$ $p$ $k$ $1,2,3,\ldots ,p-1$ $p$ $1,2,3,\ldots ,p-1,$

Důkaz lemmatu

Součin a žádné z čísel není násobkem , proto zbytek nemůže být . Všechny zbytky jsou jiné. Dokažme poslední tvrzení kontradikcí. Nechť at a dva součiny a dáme při dělení stejnými zbytky, pak je rozdíl násobkem , což je nemožné, protože to není násobek . Celkem existují různé nenulové zbytky z dělení . $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$

Protože podle výše uvedeného lemmatu jsou zbytky po dělení čísel a , 2 a , 3 a , ..., ( p − 1) a až do permutace čísla 1, 2, 3, ... , p − 1 , pak . Odtud . Poslední vztah lze redukovat na ( p − 1)! , protože všechny faktory jsou prvočísla se základem p , ve výsledku dostaneme požadovaný výrok [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}\ekviv 1{\pmod {p}}$

Důsledky a zobecnění

Jestliže je prvočíslo, pak rovnost [13] platí v poli . $p$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Jestliže je prvočíslo jiné než 2 a 5, pak číslo, jehož desítkový zápis obsahuje pouze číslice , je dělitelné . Z toho vyplývá, že pro jakékoli celé číslo , které není dělitelné ani 2, ani 5, můžete vybrat číslo skládající se pouze z devítek, které je dělitelné . Této skutečnosti se využívá v teorii znaků dělitelnosti a periodických zlomků [14] . $p$ $10^{p-1}-1$ $9$ $p$ $N$ $N$
Fermatova malá věta umožňuje najít prvočíselníky čísel tvaru a [15] . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
Zobecněním Fermatovy malé věty na algebraická čísla je věta formulovaná Schönemannem [ v roce 1839: nechť jsou kořeny normalizovaného polynomu stupně dap prvočíslo . Potom [16] . $a_{1},\tečky ,a_{d}$ $f\in \mathbb {Z} [x]$ $a_{1}^{p}+a_{2}^{p}+\tečky +a_{d}^{p}\equiv a_{1}+\tečky +a_{d}{\pmod {p))$
Fermatova Malá věta implikuje Wilsonovu větu : Přirozené číslo je prvočíslo právě tehdy, když je dělitelné p . $p>1$ $(p-1)!+1$

Důkaz Wilsonovy věty

Lagrangeova věta v teorii čísel říká, že pokud je polynom stupně dělitelný prvočíslem pro více než nesrovnatelné modulo (tj. má různé zbytky, když je děleno ) hodnot proměnné , pak je dělitelný jakoukoli hodnotou . $n$ $p$ $n$ $p$ $p$ $X$ $p$ $X$

Zvažte polynom

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

kde je prvočíslo.

p

Pak najdeme:

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

Na základě Fermatovy malé věty jsou všechna tato čísla dělitelná prvočíslem , takže srovnání má nekongruentní řešení. Na druhou stranu, stupeň polynomu je pouze z toho vyplývá, že polynom je dělitelný pro všechny hodnoty a zejména pro $p$ $G(x)\ekviv 0{\pmod {p}}$ $p-1$ $p-2;$ $G(x)$ $p$ $X,$ $x=0.$

Prostředek $G(0)=[(p-1)!+1]\ekviv 0{\pmod {p}}.$

A pokud navíc k tomu dokážeme, že pro všechna nejednoduchá přirozená , kromě , , získáme důkaz věty. [17] $n$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Aplikace

Fermatova pseudoprima a testování prvočísel

Fermatovu malou větu lze použít k testování, zda je číslo prvočíslo: pokud není dělitelné , pak je to složené číslo . Nicméně, opak Fermatovy malé věty je obecně nesprávný: jestliže a jsou prvočísla a jsou dělitelná , pak číslo může být jak prvočíslo, tak složené. V případě, že je kompozitní, nazývá se Fermatovo pseudojednoduché k bázi . $(a^{p}-a)$ $p$ $p$ $A$ $p$ $a^{p-1} - 1$ $p$ $p$ $p$ $A$

Například čínská hypotéza tvrdí, že jde o prvočíslo právě tehdy, když [18] . Zde je přímé tvrzení, že pokud je prvočíslo, pak , je speciální případ Fermatovy malé věty. Opačné tvrzení, že if , then je jednoduché, je speciálním případem inverze Fermatovy malé věty. Tento převod je nepravdivý: Sarrus v roce 1820 zjistil, že číslo je dělitelné, protože je dělitelné . Je to však složené číslo : . Jedná se tedy o pseudoprvočíslo v základu 2 [19] . $p$ $2^{p}\ekviv 2{\pmod {p}}$ $p$ $2^{p}\ekviv 2{\pmod {p}}$ $2^{p}\ekviv 2{\pmod {p}}$ $p$ $N=2^{341-1}-1$ $341$ $N$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

V obecném případě také selhává inverzní Fermatova Malá věta. Protipříkladem v obecném případě jsou Carmichaelova čísla : jedná se o čísla , která jsou v základu pseudoprimá pro všechna coprime až . Nejmenší z Carmichaelových čísel je 561. $p$ $A$ $A$ $p$

Vzhledem k tomu, že opak Fermatovy malé věty je nesprávný, splnění jeho podmínky nezaručuje, že se jedná o prvočíslo . Nicméně Fermatův malý teorém je základem Fermatova testu primálnosti [20] . Fermatův test je test pravděpodobnosti primality: pokud teorém není pravdivý, pak je číslo přesně složené, a pokud ano, pak je číslo s určitou pravděpodobností prvočíslo . Z dalších pravděpodobnostních metod lze zaznamenat Solovay-Strassenův test a Miller-Rabinův test , který se do jisté míry opírá o Fermatův malý teorém [21] . Existuje také deterministický algoritmus: Agrawal-Kayala-Saksen test . $p$

Následující dvě tvrzení jsou navíc pravdivá. Pokud pár vyhovuje porovnání , pak ho splňuje i pár čísel . Pro libovolné prvočíslo a jakékoli takové, že , je hodnota Fermatovo pseudoprvo k základu [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$

Algoritmus RSA

Fermatova malá věta se také používá při dokazování správnosti šifrovacího algoritmu RSA [2] .

Viz také

Poznámky

↑ 1 2 Vinberg, 2008 , str. 43.
↑ 1 2 3 Sagalovich, 2014 , str. 34.
↑ Encyklopedie elementární matematiky, kniha 1, Aritmetika, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961.— S. 280
↑ Z. I. Borevič, I. R. Šafarevič. Teorie čísel. — M .: Nauka, 1972. — 175 s.
↑ Gracian E. Prvočísla . Dlouhá cesta do nekonečna. - De Agostini, 2014. - T. 3. - S. 45. - 148 s. — (Svět matematiky). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Čísla - jazyk vědy, 2008 , s. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Teorie čísel prostřednictvím dotazu Archivováno 16. září 2012 na Wayback Machine . - 2006. - str. 62-63.
↑ John J. O'Connor a Edmund F. Robertson . Sir James Ivory je biografie v archivu MacTutor .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Za stránkami učebnice matematiky: Aritmetika. Algebra. Geometrie . - M . : Vzdělávání, 1996. - S. 30 . — 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Čísla - jazyk vědy, 2008 , s. 231-234.
↑ Vinberg, 2008 , str. 44.
↑ QUANTUM, 2000, č. 1, Senderov V, Spivak A. Fermatova malá věta.
↑ Akritas A. Základy počítačové algebry s aplikacemi, s. 83.
↑ Danzig, T. Čísla - jazyk vědy, 2008 , s. 232-234.
↑ QUANTUM, 2000, č. 3, Senderov V, Spivak A Fermatova malá věta
↑ Vinberg, 2008 , str. 49.
↑ Danzig, T. Čísla jsou jazykem vědy, 2008 , s. 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. Informační bezpečnost: učebnice. - M.: MIPT, 2011. - S. 236-237. — 262 s. S. — ISBN 978-5-7417-0377-9 .
↑ Testování Williams HC Primality na počítači // Ars Combin. - 1978. - Sv. T. 5 , ne. Ne. 12 . — S. 127-185 .
↑ Shitov Yu.A. Numerické metody v kryptografii.

Literatura

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Encyklopedie elementární matematiky. Svazek I: Aritmetika. — 1951.
Borevich Z. I., Shafarevich I. R. Teorie čísel . — M .: Nauka, 1972. — 510 s. Archivováno 8. ledna 2011 na Wayback Machine
Malá věta Vinberga EB Fermata a její zobecnění // Matem. osvícení - M . : Nakladatelství MTSNMO , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Fermatova malá věta" . - Kvant , 1972. - č. 10 . (nedostupný odkaz)
Danzig, T. Čísla jsou jazykem vědy . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu.V. Algoritmické problémy teorie čísel . - 1997. - Vydání. 2 , č. třetí série .
Sagalovich Yu.L. Úvod do algebraických kódů - 3. vydání, revidováno. a doplňkové - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Senderov V, Spivak A. Fermatova malá věta // Kvant. - 2000. - č. 1 .
Senderov V, Spivak A. Fermatova malá věta // Kvant. - 2000. - č. 3 .