Wilson tétele

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 1-jén felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Wilson- tétel a számelmélet egyik tétele, amely azt állítja

Ha prímszám, akkor a szám osztható -vel . Ezzel szemben, ha osztható -vel , akkor prímszámról van szó. $p$ $(p-1)!+1$ $p$ $(p-1)!+1$ $p$ $p$

Ennek a tételnek elsősorban elméleti jelentősége van, mivel a faktoriálist meglehetősen nehéz kiszámítani. Könnyebb kiszámítani , így azok az elemi tesztek , amelyek meghatározzák, hogy egy szám prím-e, Fermat tételén alapulnak , nem pedig Wilson tételén. Például a Wilson-tétel segítségével talált legnagyobb prímszám valószínűleg 1099511628401, és még optimalizált számítási megközelítés mellett is körülbelül egy napot vesz igénybe a számítások SPARC processzorokon , és a több tízezer számjegyből álló számok átmennek a primalitási teszten Fermat-tétel kevesebb, mint egy óra alatt. De ellentétben Fermat kis tételével, Wilson tétele egyszerre szükséges és elégséges feltétele az egyszerűségnek. $(p-1)!$ $a^{p-1}$ $p!$

Történelem

Ezt a tételt Ibn al-Haytham fogalmazta meg először i.sz. 1000 körül, [1] és 1770-ben Waring fogalmazta meg ezt a tételt a Cambridge-ben megjelent Meditationes Algebraicae című művében, Wilson tételét bizonyíték nélkül adja meg. Szerinte a tétel Wilson tanítványáé . A tétel bizonyítását csak 1782-ben publikálta Meditációi harmadik kiadásában. A Wilson-tétel első bizonyítékát 1771-ben Lagrange adta [2] .

Végül Euler az Opuscban. Analyt , 1. kötet , p. 329 bizonyítást adott, Gauss általánosította Wilson tételét egy összetett modul esetére. Bizonyítékok vannak arra, hogy Leibniz egy évszázaddal korábban tudott az eredményről, de soha nem publikálta.

Példa

A táblázat tartalmazza a p értékeit 2-től 31-ig, valamint a p -vel való osztás maradékát ( m - nek p -vel való osztásának maradékát m mod p -ként jelöljük ). A prímszámok zölddel vannak kiemelve . $(p-1)!$ $(p-1)!$

Maradékok táblázata modulo n

$p$	$(p-1)!$	$(p-1)!{\bmod {p}}$
2	egy	egy
3	2	2
négy	6	2
5	24	négy
6	120	0
7	720	6
nyolc	5040	0
9	40320	0
tíz	362880	0
tizenegy	3628800	tíz
12	39916800	0
13	479001600	12
tizennégy	6227020800	0
tizenöt	87178291200	0
16	1307674368000	0
17	20922789888000	16
tizennyolc	355687428096000	0
19	6402373705728000	tizennyolc
húsz	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
harminc	8841761993739701954543616000000	0
31	265252859812191058636308480000000	harminc

Bizonyítás

Bizonyíték

Megfelelőség

Legyen p prím.

1. módszer

Fontolja meg . A modulo p modulo szorzás nem nulla maradék osztályok halmaza egy csoport , majd a csoport összes elemének szorzata . Mivel egy csoport, ezért minden eleméhez egyedi inverz elem tartozik . A megfeleltetés a csoportot osztályokra osztja: ha (ami ekvivalens -val , vagyis mivel egy másodfokú egyenletnek legfeljebb két megoldása lehet), akkor az osztály egy elemet tartalmaz , ellenkező esetben az osztály két elemből áll - . Tehát, ha egy osztály egy elemet tartalmaz , akkor az összes elemének szorzata egyenlő , ha pedig az osztály 2 elemet tartalmaz, akkor az összes elemének szorzata egyenlő 1-gyel. A szorzatban az elemeket csoportosítjuk osztályok esetén a 2 elemű osztályok összes szorzata egyszerűen egyenlő 1-gyel: $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ ${\mathbb {Z}}_{p}^{{\times }}$ $a$ $a^{{-1}}:aa^{{-1}}\equiv 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 \ limits _{{a^{2}=1}}a\equiv 1\cdot (-1)\equiv -1{\pmod p}.

■

2. módszer

A csoport ciklikus , azaz van olyan elem , amelyhez bármely elemhez létezik olyan, hogy . Mivel van egy eleme, a 0-tól kezdve egészen addig, amíg a maradékok teljes csoportján végigfut az értékeken . Akkor ${\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}.

■

3. módszer

${\mathbb {Z}}_{p}^{{\times }}$ - mező , ezért benne játszódik le a Lagrange-tétel , azaz a fokpolinomnak legfeljebb gyöke van. Tekintsük polinomokat és . Mindkét polinomnak van gyöke ( ezt a Fermat-féle kis tétel kapja ), a polinomok fokai egyenlők , a vezető együtthatók azonosak. Ekkor a polinomnak legalább azonos gyöke van, de foka legfeljebb . Ennélfogva Bezout tétele szerint azonosan egyenlő nullával, azaz mindenre lesz , különösen , ami ekvivalens -val . Megkapjuk a tétel állítását -re , mivel páros, és ezért . ■ $n$ $n$ $f(x)=(x-1)\lpontok (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$

Szükség

Ha és összetett , akkor , és for , megkapjuk . $p$ $p\neq 4$ $(p-1)!\equiv 0{\pmod {p))$ $p=4$ $(4-1)!\equiv 2{\pmod 4}$

Az elegendőség geometriai bizonyítéka

Legyen p prímszám. Számozzuk át egy szabályos p -gon csúcsait a körvonal bejárásának sorrendjében: 1, 2, 3, ..., p . Ha átlókkal sorba kötjük őket egyen, majd kettőn, hárman stb., akkor a 123... szabályos sokszögen kívül ( p − 2) 135..., 147. sokszögeket is kapunk. ., 159.. stb. Ezek a ( p − 1) sokszögek páronként azonosak, mivel a csúcsokat k -n keresztül és ( p − k − 2)-n keresztül összekötve azonos sokszögeket kapunk. Az így kapott különböző szabályos sokszögek száma ; $(p-1)/2$
Ha a csúcsokat más sorrendben kötjük össze, például 13245... sorrendben, akkor egy szabálytalan sokszöget kapunk; Ezt a sokszöget úgy forgatva, hogy csúcsainak számait a sorrendben következő számok helyettesítik (a p számot eggyel helyettesítjük), p szabálytalan sokszöget kapunk. A fenti példában ezek 13245..., 24356..., 35467..., ..., 2134 sokszögek lesznek... Ha az összes lehetséges szabálytalan sokszöget így alakítjuk ki, akkor számuk többszöröse lesz. p , de, mint a szabályos sokszögek esetében, két azonos; két csúcssorozat, közvetlen és inverz, amelyek ugyanazt a sokszöget adják;
Ha a 23... csúcsok összes lehetséges permutációját ( p − 1) elvégezzük a 123... csúcsok sorozatában , akkor megkapjuk az összes lehetséges (szabályos és irreguláris) sokszöget; számuk lesz ; párban ismét azonosak lesznek, tehát valós számuk ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ $(p-1)!/2$
Az 1. és 3. pont eredményeit összehasonlítva azt látjuk, hogy a szabálytalan sokszögek száma egyenlő lesz: . A 2. ponttól kezdve ennek a számnak oszthatónak kell lennie p -vel ; tehát ( p − 1)! + 1 többszörös p .: ■ ${\megjelenítési stílus 1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)}$

Alkalmazás

A Wilson-tételt használjuk

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

Egy p = 2 m + 1 páratlan prímre azt kapjuk

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}}.

Ennek eredményeként

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

Ezt a tényt egy jól ismert eredmény bizonyítására használhatjuk: minden olyan p prím esetén , amelynél p ≡ 1 (mod 4), a (−1) szám egy négyzet ( másodfokú maradék ) mod p . Valóban, legyen p = 4 k + 1 valamilyen természetes k esetén . Ekkor m = 2 k , tehát

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

A Wilson-tételt prímszámok generálására használják, de a gyakorlati felhasználáshoz túl lassú.

Általánosítás

Példaként használva Euler tételét , próbáljuk meg általánosítani a Wilson-tételt a p = n esetre , ahol n tetszőleges természetes szám. Egyszerű változtatás ( p − 1)! az n -nél kisebb és n -hez relatív prímszámok n 1 n 2 ... n k szorzata nem felel meg: n = 8 esetén ez a szorzat 1 × 3 × 5 × 7 = 105, 106 pedig nem osztható 8-cal. De kiderül, hogy vagy n 1 n 2 … n k + 1, vagy n 1 n 2 … n k − 1 szükségszerűen osztható n -nel .

Tekintsük az n -nél kisebb és n -hez viszonyított prímszámok E n halmazát . Az ab halmaz két elemének szorzata alatt a szokásos ab szorzat n -nel való osztásának maradékát értjük . Nyilvánvaló, hogy ha a , b E n -hez tartozik , akkor ab E n - hez tartozik . Az E n halmaz a szorzás műveletére nézve egy csoport. Ellentétben azzal az esettel, amikor n prím, az E n csoport tartalmazhat olyan elemeket, amelyek nem egyenlők 1-gyel és ( n − 1) úgy, hogy négyzetük egyenlő 1-gyel: például ha n = 8, akkor 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. Ezért általános esetben az E n -ből származó összes elem szorzata nem egyenlő ( n − 1). Mutassuk meg, hogy akkor egyenlő 1-gyel.

Az E n csoport egy a elemét speciálisnak nevezzük, ha aa = 1. Ebben az esetben az n − a elem is speciális. Ezért az E n csoport páros számú speciális elemet tartalmaz: ( a , n − a ) az ilyen elemek halmaza, és egyetlen elem sem lehet pár önmagának. Legyen n 1 , n 2 , …, n k az E n csoport összes eleme , azaz n-nél kisebb és n -hez képest relatív prímszámok teljes halmaza . A nem speciális elemek halmazát kölcsönösen inverzek párjaira osztjuk, így az ilyen elemek szorzata egyenlő 1-gyel. Másrészt az ( a , n − a ) párt alkotó speciális elemek szorzata egyenlő n − 1-gyel. Mivel ( n − 1)( n − 1) = 1, akkor az összes speciális elem szorzata 1 vagy n − 1, attól függően, hogy hány párja van az ( a , n − a ) páros vagy páratlan. ■

A tételt először Gauss bizonyította és általánosította , bármely n > 2 esetén, minden n -t meg nem haladó természetes szám és n -re másodlagos szám szorzatára összehasonlítás történik:

\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}}

ahol páratlan prímszám, természetes mutató. $p$ $\alpha$

Később a Wilson-tétel egy másik formális általánosítására is sor került (V. Vinograd):

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

A Wilson-tételt kapjuk. $m=1$

Amikor kiderül , i.e. $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}}$ , ha $p\equiv 1{\pmod {4}}$

és

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

Lásd még

Jegyzetek

↑ John J. O'Connor és Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (angolul) egy életrajz a MacTutor archívumában .
↑ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau consultant les nombres premiers" Archiválva 2022. május 11-én a Wayback Machine -nál ( Prómszámokra vonatkozó új tétel bizonyítása), Nouveaux Mémoires de l'Académie et Bele-des Sciencesre . Berlin), vol. 2, 125-137. oldal (1771)

Irodalom

Bukhshtab A. A. Számelmélet, 2. kiadás, M., 1966
Trost E. Prímszámok , ford. németből, M., 1959
Vinogradov I.M. A számelmélet alapjai . - 5. kiadás - M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher és C. Pomerance The Prime Glossary
Ore, O. Számelmélet és története. McGraw-Hill, 1948.
Boncskovszkij R. N. és Csisztjakov I. I. Matematikai oktatás, 01. szám

Szótárak és enciklopédiák	Nagy dán Nagy Szovjet (1 kiadás) Britannica (online)