Wilsonin lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1. lokakuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Wilsonin lause on lukuteorian lause, joka väittää tämän

Jos on alkuluku, niin luku on jaollinen . Päinvastoin, jos se on jaollinen , niin se on alkuluku. $s$ $(p-1)!+1$ $s$ $(p-1)!+1$ $s$ $s$

Tällä lauseella on pääasiassa teoreettinen merkitys, koska faktoriaalia on melko vaikea laskea. Se on helpompi laskea , joten alkeistestit, jotka määrittävät, onko luku alkuluku, perustuvat Fermatin lauseeseen, eivät Wilsonin lauseeseen. Esimerkiksi suurin Wilsonin lauseella löydetty alkuluku on todennäköisesti 1099511628401, ja jopa optimoidulla laskentamenetelmällä laskutoimitukset kestävät noin päivän SPARC-prosessoreilla ja kymmenientuhansien numeroiden luvut läpäisevät primaalisuustestin käyttämällä Fermatin lause alle tunnissa. Mutta toisin kuin Fermatin pieni lause, Wilsonin lause on sekä välttämätön että riittävä ehto yksinkertaisuudelle. $(p-1)!$ $a^{p-1}$ $p!$

Historia

Tämän lauseen esitti ensimmäisen kerran Ibn al-Haytham noin 1000 jKr. [1] ja vuonna 1770 Waring muotoili tämän lauseen Meditationes Algebraicaessa , joka julkaistiin Cambridgessa. Hän esittää Wilsonin lauseen ilman todisteita. Hänen mukaansa lause kuuluu hänen oppilaalleen Wilsonille . Hän julkaisi lauseen todisteen vasta Meditationes -teoksensa kolmannessa painoksessa vuonna 1782. Ensimmäisen todisteen Wilsonin lauseesta antoi vuonna 1771 Lagrange [2] .

Lopuksi Euler Opuscissa. Analyt , osa 1, s. 329 antoi todisteen, Gauss yleisti Wilsonin lauseen komposiittimoduulin tapaukseen. On näyttöä siitä, että Leibniz tiesi tuloksesta sata vuotta aikaisemmin, mutta ei koskaan julkaissut sitä.

Esimerkki

Taulukko sisältää p :n arvot välillä 2-31, sekä p :llä jaon loppuosan ( m :n p :llä jaon loppuosa merkitään m mod p ). Alkuluvut on korostettu vihreällä . $(p-1)!$ $(p-1)!$

Jäännöstaulukko modulo n

$s$	$(p-1)!$	${\näyttötyyli (p-1)!{\bmod {p}}}$
2	yksi	yksi
3	2	2
neljä	6	2
5	24	neljä
6	120	0
7	720	6
kahdeksan	5040	0
9	40320	0
kymmenen	362880	0
yksitoista	3628800	kymmenen
12	39916800	0
13	479001600	12
neljätoista	6227020800	0
viisitoista	87178291200	0
16	1307674368000	0
17	20922789888000	16
kahdeksantoista	355687428096000	0
19	6402373705728000	kahdeksantoista
kaksikymmentä	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
kolmekymmentä	8841761993739701954543616000000	0
31	265252859812191058636308480000000	kolmekymmentä

Todiste

Riittävyys

Olkoon p alkuluku.

Menetelmä 1

Harkitse . Nollasta poikkeavien jäännösluokkien joukko modulo p modulo kertolasku on ryhmä , ja se on sitten ryhmän kaikkien elementtien tulo . Koska on ryhmä, niin jokaiselle sen elementille on ainutlaatuinen käänteiselementti . Vastaus jakaa ryhmän luokkiin: if (joka on ekvivalentti , eli koska toisen asteen yhtälöllä voi olla enintään kaksi ratkaisua), niin luokka sisältää yhden alkion , muuten luokka koostuu kahdesta alkiosta - . Joten jos luokka sisältää yhden alkion , niin sen kaikkien alkioiden tulo on yhtä suuri ja jos luokka sisältää 2 alkiota, niin sen kaikkien alkioiden tulo on yhtä suuri kuin 1. Nyt tulossa elementit ryhmitellään luokat, kaikki 2-elementtiluokkien tuotteet ovat yksinkertaisesti yhtä suuria kuin 1: $(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 \ rajat _{{a^{2}=1}}a\equiv 1\cdot (-1)\equiv -1{\pmod p}.

■

Menetelmä 2

Ryhmä on syklinen , eli siinä on sellainen elementti , että mille tahansa elementille on olemassa sellainen, että . Koska siinä on elementti, se kulkee arvojen läpi 0:sta siihen asti, kun se kulkee koko jäännösryhmän läpi. Sitten ${\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}.

■

Menetelmä 3

${\mathbb {Z}}_{p}^{{\times }}$ - kenttä , joten siinä tapahtuu Lagrangen lause eli astepolynomilla ei ole enempää kuin juuria. Harkitse polynomeja ja . Molemmilla polynomeilla on juuret (sillä tämä saadaan Fermatin pienellä lauseella ), polynomien asteet ovat yhtä suuret , johtavat kertoimet ovat samat. Tällöin polynomilla on vähintään samat juuret, mutta sen aste on enintään . Siksi Bezoutin lauseen mukaan se on identtisesti yhtä suuri kuin nolla, eli kaikille se on erityisesti , joka vastaa . Saamme lauseen lauseen , koska se on parillinen ja siten . ■ $n$ $n$ $f(x)=(x-1)\lpisteet (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$

Tarve

Jos ja on yhdistetty , niin , ja for , saamme . $s$ $p\neq 4$ ${\näyttötyyli (p-1)!\equiv 0{\pmod {p))}$ $p=4$ $(4-1)!\equiv 2{\pmod 4}$

Geometrinen todistus riittävyydestä

Olkoon p alkuluku. Numeroidaan uudelleen säännöllisen p -gonin kärjet ääriviivan kulkemisjärjestyksessä: 1, 2, 3, ..., p . Jos yhdistämme ne diagonaaleilla sarjaan yhden, sitten kahden, kolmen jne. kautta, niin säännöllisen monikulmion 123... lisäksi saadaan myös ( p − 2) polygonit 135..., 147.. ., 159.. jne. Nämä ( p − 1) polygonit ovat pareittain identtisiä, koska yhdistämällä kärjet k :n ja ( p − k − 2) kautta saadaan identtiset monikulmiot. Tällä tavalla saatujen erilaisten säännöllisten polygonien lukumäärä on ; $(p-1)/2$
Jos yhdistämme kärjet jossain muussa järjestyksessä, esimerkiksi järjestyksessä 13245..., niin saadaan epäsäännöllinen monikulmio; Kiertämällä tätä monikulmiota niin, että sen kärkien luvut korvataan järjestyksessä seuraavalla numerolla (luku p korvataan yhdellä), saadaan p epäsäännöllistä monikulmiota. Yllä olevassa esimerkissä nämä ovat polygoneja 13245..., 24356..., 35467..., ..., 2134... Jos muodostamme kaikki mahdolliset epäsäännölliset monikulmiot tällä tavalla, niin niiden lukumäärä on kerrannainen p : stä , mutta, kuten säännöllisten monikulmioiden tapauksessa, ne ovat kaksi identtistä; se on kaksi kärkijonoa, suora ja käänteinen, jotka antavat saman monikulmion;
Jos teemme kaikki mahdolliset permutaatiot ( p − 1) pisteille 23... pisteiden 123... jonossa , niin saadaan kaikki mahdolliset (säännölliset ja epäsäännölliset) monikulmiot; niiden lukumäärä on ; ne ovat jälleen identtisiä pareittain, joten niiden todellinen lukumäärä on ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ ${\näyttötyyli (p-1)!/2}$
Vertaamalla pisteiden 1 ja 3 tuloksia, näemme, että epäsäännöllisten polygonien määrä on yhtä suuri kuin: . Pisteestä 2 alkaen tämän luvun on oltava jaollinen p :llä ; siis ( p − 1)! + 1 moninkertainen p .: ■ ${\näyttötyyli 1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)}$

Sovellus

Käytämme Wilsonin lausetta

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

Parittomalla alkuluvulla p = 2 m + 1 saamme

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

Tuloksena

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

Voimme käyttää tätä tosiasiaa todistamaan hyvin tunnetun tuloksen: mille tahansa alkuluvulle p , jonka p ≡ 1 (mod 4), luku (−1) on neliö ( neliöjäännös ) mod p . Todellakin, olkoon p = 4 k + 1 jollekin luonnolliselle k :lle . Silloin m = 2 k , siis

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

Wilsonin lausetta käytetään alkulukujen luomiseen, mutta se on liian hidas käytännön käyttöön.

Yleistys

Käyttämällä esimerkkinä Eulerin lausetta yritetään yleistää Wilsonin lause tapaukseen p = n , jossa n on mielivaltainen luonnollinen luku. Yksinkertainen muutos ( p − 1)! kaikkien lukujen, jotka ovat pienempiä kuin n ja suhteellisesti alkuluku n :lle, tulo n 1 n 2 ... n k ei läpäise: jos n = 8, tämä tulo on 1 × 3 × 5 × 7 = 105 ja 106 on ei jaollinen 8:lla. Mutta käy ilmi, että joko n 1 n 2 … n k + 1 tai n 1 n 2 … n k − 1 on välttämättä jaollinen n :llä .

Tarkastellaan n:tä pienempien lukujen joukkoa E n ja suhteellisesti alkuluku n :lle . Tämän joukon ab kahden alkion tulon alla tarkoitamme jäännöstä tavallisen tulon ab jakamisesta n: llä . On selvää, että jos a , b kuuluu En : ään , niin ab kuuluu En : ään . Joukko E n kertolaskuoperaation suhteen on ryhmä. Toisin kuin tapauksessa, jossa n on alkuluku, ryhmä E n voi sisältää alkioita, jotka eivät ole yhtä suuria kuin 1 ja ( n − 1) siten, että niiden neliö on yhtä suuri kuin 1: esimerkiksi jos n = 8, niin 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. Siksi yleisessä tapauksessa kaikkien elementtien tulo E n : stä ei ole yhtä suuri kuin ( n − 1). Osoitetaan, että silloin se on yhtä suuri kuin 1.

Kutsumme ryhmän E n alkiota a erikoiseksi, jos aa = 1. Tässä tapauksessa elementti n − a on myös erityinen. Siksi ryhmä E n sisältää parillisen määrän erikoisalkioita: ( a , n − a ) on tällaisten alkioiden joukko, eikä mikään alkio voi olla itselleen pari. Olkoon n 1 , n 2 , …, n k kaikki ryhmän E n alkiot , eli täydellinen joukko lukuja, jotka ovat pienempiä kuin n ja suhteellisesti alkuluku n :lle . Elementtien joukko, jotka eivät ole erityisiä, jaetaan keskenään käänteispareihin, joten tällaisten alkioiden tulo on yhtä suuri kuin 1. Toisaalta parin ( a , n − a ) muodostavien erikoisalkioiden tulo. on yhtä suuri kuin n − 1. Koska ( n − 1)( n − 1) = 1, niin kaikkien erikoisalkioiden tulo on 1 tai n − 1 riippuen siitä, onko muotoa ( a , n − a ) on parillinen tai pariton. ■

Lauseen osoitti ja yleisti ensin Gauss , minkä tahansa n > 2:n osalta kaikkien luonnollisten lukujen tulolle, jotka eivät ylitä n : ää ja koprime n :stä , suoritetaan vertailu:

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

missä on pariton alkuluku, on luonnollinen indikaattori. $s$ $\alpha$

Myöhemmin Wilsonin lauseesta löydettiin toinen muodollinen yleistys (V. Vinograd):

${\näyttötyyli (pm)!*(m-1)!\equiv (-1)^{m}{\pmod {p))}$

Kohdassa , Wilsonin lause saadaan. $m = 1$

Kun käy ilmi , ts. $m=\left({\frac {p+1}{2}}\oikea)$ $\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}}$ , jos $p\equiv 1{\pmod {4}}$

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

Katso myös

Muistiinpanot

↑ John J. O'Connor ja Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (englanniksi) on elämäkerta MacTutor- arkistossa .
↑ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau relatedant les nombres premiers" Arkistoitu 11. toukokuuta 2022 Wayback Machine -sovellukseen (Proof uudelle alkulukuja koskevalle lauseelle), Nouveaux Mémoires de l'Académie Royale-des Sciencesre et Bele-des Sciencesre Berliini), voi. 2, sivut 125-137 (1771)

Kirjallisuus

Bukhshtab A. A. Numeroteoria , 2. painos, M., 1966
Trost E. Alkuluvut , käänn. saksasta, M., 1959
Vinogradov I.M. Lukuteorian perusteet . - 5. painos - M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher ja C. Pomerance The Prime Glossary
Ore, O. Numeroteoria ja sen historia. McGraw-Hill, 1948.
Bonchkovsky R. N. ja Chistyakov I. I. Matemaattinen koulutus, numero 01

Sanakirjat ja tietosanakirjat	Suuri tanskalainen Suuri Neuvostoliitto (1 painos) Britannica (verkossa)