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. |
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.
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ä.
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ä .
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ä |
Olkoon p alkuluku.
Menetelmä 1Harkitse . 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:
Menetelmä 2Ryhmä 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
Menetelmä 3- 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 . ■
Jos ja on yhdistetty , niin , ja for , saamme .
Parittomalla alkuluvulla p = 2 m + 1 saamme
Tuloksena
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
Wilsonin lausetta käytetään alkulukujen luomiseen, mutta se on liian hidas käytännön käyttöön.
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:
missä on pariton alkuluku, on luonnollinen indikaattori.
Myöhemmin Wilsonin lauseesta löydettiin toinen muodollinen yleistys (V. Vinograd):
Kohdassa , Wilsonin lause saadaan.
Kun käy ilmi , ts.
, jos
ja
, jos
![]() |
|
---|