Wilsonova věta

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. října 2021; kontroly vyžadují 3 úpravy .

Wilsonův teorém je teorém v teorii čísel , který říká, že

Pokud je prvočíslo, pak je číslo dělitelné . Naopak, pokud je dělitelné , pak je to prvočíslo. $p$ $(p-1)!+1$ $p$ $(p-1)!+1$ $p$ $p$

Tato věta má hlavně teoretický význam, protože faktoriál je poměrně obtížné vypočítat. Je snazší vypočítat , takže elementární testy , které určují, zda je číslo prvočíslo, jsou založeny na Fermatově větě , nikoli na Wilsonově větě. Například největší prvočíslo nalezené pomocí Wilsonova teorému bude pravděpodobně 1099511628401 ai s optimalizovaným přístupem k výpočtu bude výpočet na procesorech SPARC trvat asi den a čísla s desítkami tisíc číslic projdou testem primality pomocí Fermatova věta za méně než hodinu. Ale na rozdíl od Fermatovy malé věty je Wilsonova věta nezbytnou i postačující podmínkou jednoduchosti. $(p-1)!$ $a^{p-1}$ $p!$

Historie

Tuto větu poprvé vyslovil Ibn al-Haytham kolem roku 1000 n. l. [1] a v roce 1770 Waring tuto větu formuloval ve svém Meditationes Algebraicae publikovaném v Cambridge, Wilsonovu větu uvádí bez důkazu. Věta podle něj patří jeho studentovi Wilsonovi . Důkaz teorému publikoval až ve třetím vydání svých Meditationes v roce 1782. První důkaz Wilsonovy věty podal v roce 1771 Lagrange [2] .

Nakonec Euler v Opusc. Analyt , svazek 1, str. 329 poskytl důkaz, Gauss zobecnil Wilsonovu větu na případ složeného modulu. Existují důkazy, že Leibniz věděl o výsledku o století dříve, ale nikdy jej nezveřejnil.

Příklad

Tabulka obsahuje hodnoty pro p od 2 do 31 a také zbytek dělení p (zbytek dělení m p je označen jako m mod p ) . Prvočísla jsou zvýrazněna zeleně . $(p-1)!$ $(p-1)!$

Tabulka zbytků modulo n

$p$	$(p-1)!$	$(p-1)!{\bmod {p}}$
2	jeden	jeden
3	2	2
čtyři	6	2
5	24	čtyři
6	120	0
7	720	6
osm	5040	0
9	40320	0
deset	362880	0
jedenáct	3628800	deset
12	39916800	0
13	479001600	12
čtrnáct	6227020800	0
patnáct	87178291200	0
16	1307674368000	0
17	20922789888000	16
osmnáct	355687428096000	0
19	6402373705728000	osmnáct
dvacet	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	155112100433330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
třicet	8841761993739701954543616000000	0
31	265252859812191058636308480000000	třicet

Důkaz

Přiměřenost

Nechť p je prvočíslo.

Metoda 1

Zvažte . Množina nenulových tříd zbytků modulo p modulo násobení je grupa , a pak je součin všech prvků grupy . Protože je skupina, pak pro každý její prvek existuje jedinečný inverzní prvek . Korespondence rozděluje skupinu do tříd: if (což je ekvivalentní , to znamená , protože rovnice druhého stupně nemůže mít více než dvě řešení), pak třída obsahuje jeden prvek , jinak se třída skládá ze dvou prvků - . Pokud tedy třída obsahuje jeden prvek , pak je součin všech jejích prvků roven , a pokud třída obsahuje 2 prvky, pak je součin všech jejích prvků roven 1. Nyní v součinu prvky seskupíme podle třídy jsou všechny produkty podle 2prvkových tříd jednoduše rovny 1: $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ ${\mathbb {Z}}_{p}^{{\times }}$ $A$ $a^{{-1}}:aa^{{-1}}\ekviv 1{\pmod p}$ $a\to a^{{-1}}$ $a=a^{{-1}}$ $a^{2}=1$ $a\in\{1,-1\}$ $A$ $\{a,a^{{-1}}\}$ $A$ $A$ $(p-1)!$

(p-1)!\equiv \prod \limits _{{a^{2}=1}}a\cdot \prod \limits _{{a^{2}\neq 1}}a\equiv \prod \ limity _{{a^{2}=1}}a\equiv 1\cdot (-1)\equiv -1{\pmod p}.

■

Metoda 2

Skupina je cyklická , tj. existuje prvek takový , že pro jakýkoli prvek existuje takový , že . Protože má prvek, prochází hodnotami od 0 do kdy prochází celou skupinou zbytků. Pak ${\mathbb {Z}}_{p}^{{\times }}$ $G$ $A$ $k$ $a=g^{k}$ ${\mathbb {Z}}_{p}^{{\times }}$ $p-1$ $k$ $p-1$ $A$

(p-1)!\equiv g^{1}g^{2}\ldots g^{{p-1}}\equiv g^{{1+2+\ldots +(p-1)}}= g^{{{\frac {p-1}{2}}p}}\equiv (-1)^{p}\equiv -1{\pmod p}.

■

Metoda 3

${\mathbb {Z}}_{p}^{{\times }}$ - pole , proto se v něm odehrává Lagrangeova věta , tj. polynom stupně nemá více než kořeny. Zvažte polynomy a . Oba polynomy mají kořeny (protože to je získáno Fermatovou malou větou ), stupně polynomů jsou stejné , vedoucí koeficienty jsou stejné. Pak má polynom minimálně stejné kořeny, ale jeho stupeň je maximálně . Podle Bezoutovy věty je tedy shodně roven nule, tj. pro všechny bude , zejména , což je ekvivalentní . Získáme tvrzení věty pro , protože je sudé a tedy . ■ $n$ $n$ $f(x)=(x-1)\ldots (x-(p-1))$ $g(x)=x^{{p-1}}-1$ $1,2,\ldots ,p-1$ $g(x)$ $p-1$ $h(x)=f(x)-g(x)$ $p-1$ $p-2$ $h(x)$ $X$ $f(x)=g(x)$ $f(0)=g(0)$ $(-1)^{{p-1}}(p-1)!\equiv -1{\pmod p}$ $p>2$ $p-1$ $(-1)^{{p-1}}=1$

Potřeba

Jestliže a je složené , pak , a pro , dostaneme . $p$ $p\neq 4$ $(p-1)!\equiv 0{\pmod {p))$ $p=4$ $(4-1)!\ekviv 2{\pmod 4}$

Geometrický důkaz dostatečnosti

Nechť p je prvočíslo. Přečíslujme vrcholy pravidelného p -úhelníku v pořadí procházení vrstevnice: 1, 2, 3, ..., p . Spojíme-li je úhlopříčkami v sérii přes jednu, pak přes dvě, přes tři atd., pak kromě pravidelného mnohoúhelníku 123... dostaneme ( p − 2) mnohoúhelníky 135..., 147.. ., 159.. atd. Tyto ( p − 1) polygony jsou párově shodné, protože spojením vrcholů přes k a přes ( p − k − 2) získáme shodné polygony. Počet různých pravidelných polygonů získaných tímto způsobem je ; $(p-1)/2$
Spojíme-li vrcholy v nějakém jiném pořadí, například v pořadí 13245..., pak dostaneme nepravidelný mnohoúhelník; otočením tohoto mnohoúhelníku tak, aby se čísla jeho vrcholů nahradila čísly následujícími v pořadí (číslo p se nahradí jedničkou), dostaneme p nepravidelných mnohoúhelníků. Ve výše uvedeném příkladu to budou polygony 13245..., 24356..., 35467..., ..., 2134... Pokud takto vytvoříme všechny možné nepravidelné polygony, pak jejich počet bude násobkem z p , ale jako v případě pravidelných mnohoúhelníků jsou dva totožné; jsou to dvě sekvence vrcholů, přímá a inverzní, které dávají stejný mnohoúhelník;
Pokud provedeme všechny možné permutace ( p − 1) vrcholů 23... v posloupnosti vrcholů 123... , pak dostaneme všechny možné (pravidelné i nepravidelné) polygony; jejich počet bude ; ve dvojicích budou opět totožné, takže jejich reálné číslo je ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ $(p-1)!/2$
Porovnáním výsledků z bodů 1 a 3 vidíme, že počet nepravidelných polygonů bude roven: . Od bodu 2 musí být toto číslo dělitelné p ; proto ( p − 1)! + 1 násobek p .: ■ $1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)$

Aplikace

Použijeme Wilsonovu větu

1\cdot 2\cdots (p-1)\equiv -1{\pmod {p)).

Pro liché prvočíslo p = 2 m + 1 dostáváme

1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (pm)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m \cdot (-m)\equiv -1{\pmod {p}}.

Jako výsledek

\prod _{j=1}^{m}j^{2}\equiv (-1)^{m+1}{\pmod {p)).

Tuto skutečnost můžeme použít k prokázání známého výsledku: pro libovolné prvočíslo p takové, že p ≡ 1 (mod 4), číslo (−1) je čtverec ( kvadratický zbytek ) mod p . Nechť p = 4 k + 1 pro nějaké přirozené k . Pak m = 2 k , tedy

{\biggl (}\prod _{j=1}^{2k}\ j{\biggr )}^{2}=\prod _{j=1}^{2k}j^{2}\ ekviv (-1)^{2k+1}=-1{\pmod {p)).

Wilsonova věta se používá ke generování prvočísel, ale pro praktické použití je příliš pomalá.

Generalizace

Pomocí Eulerovy věty jako příkladu se pokusme zobecnit Wilsonovu větu na případ p = n , kde n je libovolné přirozené číslo. Jednoduchá změna ( p − 1)! součin n 1 n 2 ... n k všech čísel menších než n a relativně prvočíselných k n neprojde: v případě n = 8 je tento součin 1 × 3 × 5 × 7 = 105 a 106 je nedělitelné 8. Ale ukazuje se, že buď n 1 n 2 … n k + 1, nebo n 1 n 2 … n k − 1 je nutně dělitelné n .

Uvažujme množinu E n čísel menších než n a relativně prvočíselných k n . Pod součinem dvou prvků této množiny ab rozumíme zbytek dělení obvyklého součinu ab číslem n . Je jasné, že pokud a , b patří E n , pak ab patří E n . Množina E n vzhledem k operaci násobení je grupa. Na rozdíl od případu, kdy n je prvočíslo, grupa E n může obsahovat prvky, které se nerovnají 1 a ( n − 1), takže jejich druhá mocnina je rovna 1: například, když n = 8, pak 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. V obecném případě tedy součin všech prvků z E n není roven ( n − 1). Ukažme, že pak se rovná 1.

Prvek a ze skupiny E n nazýváme speciální, jestliže aa = 1. V tomto případě je speciální také prvek n − a . Proto skupina E n obsahuje sudý počet speciálních prvků: ( a , n − a ) je množina takových prvků a žádný prvek nemůže být párem sám o sobě. Nechť n 1 , n 2 , …, n k jsou všechny prvky grupy E n , tj. úplná množina čísel menších než n a relativně prvočíselných k n . Množina prvků, které nejsou speciální, je rozdělena do dvojic vzájemně inverzních, takže součin takových prvků je roven 1. Na druhou stranu součin speciálních prvků, které tvoří dvojici ( a , n − a ) se rovná n − 1. Protože ( n − 1)( n − 1) = 1, pak je součin všech speciálních prvků roven 1 nebo n − 1, podle toho, zda počet dvojic tvaru ( a , n − a ) je sudé nebo liché. ■

Větu poprvé dokázal a zobecnil Gauss , pro libovolné n > 2, pro součin všech přirozených čísel nepřesahujících n a současně s n , dochází ke srovnání:

\prod _{{k=1 \atop (k,n)=1}}^{{n}}\!\!k\equiv {\begin{cases}-1{\pmod {n)),&n= 4,\;p^{\alpha },\;2p^{\alpha }\,;\\\;\;\,1{\pmod {n)),&n\neq 4,\;p^{\ alfa },\;2p^{\alpha }\,,\end{cases}}

kde je liché prvočíslo, je přirozený indikátor. $p$ $\alpha$

Později bylo nalezeno další formální zobecnění Wilsonovy věty (V. Vinograd):

$(pm)!*(m-1)!\equiv (-1)^{m}{\pmod {p))$

V , je získán Wilsonův teorém. $m=1$

Když se ukáže , tj. $m=\left({\frac {p+1}{2}}\right)$ $\left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\left({\frac {p-1}{2}}\right )}\equiv 0{\pmod {p}}$

$\left({\frac {p-1}{2}}\right)!^{2}+1\equiv 0{\pmod {p}}$ , pokud $p\equiv 1{\pmod {4}}$

$\left({\frac {p-1}{2}}\right)!^{2}-1\equiv 0{\pmod {p}}$ , pokud $p\equiv 3{\pmod {4}}$

Viz také

Poznámky

↑ John J. O'Connor a Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (anglicky) je biografie v archivu MacTutor .
↑ Joseph Louis Lagrange, „Demonstration d'un théorème nouveau dotyčný les nombres premiers“ Archivováno 11. května 2022 na Wayback Machine (Důkaz nového teorému týkajícího se prvočísel), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles- Berlín), sv. 2, strany 125-137 (1771)

Literatura

Bukhshtab A. A. Teorie čísel, 2. vydání, M., 1966
Trost E. Prvočísla, přel. z němčiny, M., 1959
Vinogradov I.M. Základy teorie čísel . - 5. vyd. - M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher a C. Pomerance The Prime Glossary
Ore, O. Teorie čísel a její historie. McGraw-Hill, 1948.
Bonchkovsky R. N. a Chistyakov I. I. Matematické vzdělávání, číslo 01

Slovníky a encyklopedie	Velká dánština Velký sovět (1 ed.) Britannica (online)