Alkulukuja generoiva funktio

Muistaakseni joku luennoitsija joskus sanoi, että ei ole olemassa sellaista funktiota, joka palauttaisi ainoastaan alkulukuja. (Ja on totta että sellaista rationaalista algebrallista funktiota ei ole.) Tässä nyt kuitenkin olisi yksi alkulukuja tuottava funktio:

missä

B(x,y) = x(y+1)-(y!+1).

Väite:

Funktio f palauttaa vain alkulukuja, ja jokaisen parittoman alkuluvun tarkalleen yhdellä syötteellä (x,y), kun x ja y ovat positiivisia kokonaislukuja.

Tarkoitus olisi nyt todistaa tämä väite. Kokeilemalla funktiota pienillä kokonaislukuargumenteilla saadaan tulokseksi

   f(1,1) = 2    f(2,1) = 2
   f(1,2) = 3    f(2,2) = 2
   f(1,3) = 2    f(2,3) = 2
   f(1,4) = 2    ...
   ...
   ...
   f(5,4) = 5
   ...

Ainakin alkuluvut 2,3 ja 5 löytyivät, mutta tulos on melkein aina 2. Seuraavia alkulukuja saakin sitten etsiä. Esimerkiksi 7 = f( 103, 6 ) ja 11 = f( 329891, 10 ). Jo näistä näytteistä voi arvata, että jos f( x, y ) > 2, niin funktion arvo on y + 1. Vielä ennen asiaan menemistä ote funktion kuvaajasta, joka ei anna mitään lisäinformaatiota mutta näyttää kivalta:

Funktion f kuvaaja

Väitteen todistus

Helposti nähdään, että f( x, y ) > 2 täsmälleen silloin, kun osoittajassa oleva lauseke ei ole nolla. Tämä taas vaatii, että y > 1 ja että lauseke itseisarvomerkkien välissä < 0. Koska kaikki käsiteltävät luvut ovat kokonaislukuja, täytyy olla B( x, y ) = 0. Jos tämä ehto täyttyy, niin

kuten yllä jo uumoiltiin. Merkitään p = y - 1, jolloin voidaan kirjoittaa alkuperäisen väitteen kanssa yhtäpitävä väite muodossa

Kaikille alkuluvuille p on olemassa (tietenkin 1-käsitteinen) luonnollinen luku x siten että xp - ( p - 1 )! = 1. Lisäksi tällaista lukua x ei ole olemassa, jos p on koottu luku.

Toisin sanoen, kun p > 1 niin

p | (p-1)! + 1 p on alkuluku,

missä merkintä m | n tarkoittaa, että n on jaollinen m:llä. Tämä väite tunnetaan nimellä Wilsonin teoreema. Teoreema on julkaistu ensi kertaa vuonna 1770, ja se on nimetty John Wilsonin (1741-1793) mukaan. Teoreeman todisti ensimmäisenä Lagrange (1736-1813). [1]

Toiseen suuntaan implikaation todistus on helppo ja toiseen suuntaan hauska (ja/tai tuskallinen) keksiä. (Ei kannata lukea pidemmälle, jos ei halua pilata iloaan...)

Ensin helppo suunta: Todistetaan väitteen

p | (p-1)! + 1 p on alkuluku,

kanssa yhtäpitävä väite

p ei ole alkuluku (p-1)! + 1 ei ole jaollinen p:llä (*)

Oletetaan, että p = mn, missä 1 < m n < p-1. Jos p = 4, väite (*) on tosi sillä 3! + 1 = 7 ei ole jaollinen neljällä. Olkoon nyt p > 4. Jos n = m, niin n < p/2. (Sillä n p/2 2n p = n² 2 n p = 1 tai p = 4.) Nyt 2n < p, jolloin n ja 2n ovat molemmat ( p - 1 )!:n tekijöitä, mistä seuraa että p = 2n²/2 | ( p - 1 )!. Jos taas m < n, niin m | ( p - 1 )! ja n | ( p - 1 )!, jolloin p | ( p - 1 )!. Siispä p ei voi olla tekijänä yhtä suuremmassa luvussa ( p - 1 )! + 1.

Toiseen suuntaan todistus on kinkkisempi. Tässä olevan version keksimiseen kului vajaa vuosi. Varmaan joku osaisi todistaa asian helpomminkin...

Merkintä n m (mod p) tarkoittaa, että m-n on jaollinen p:llä. Jos p käy ilmi asiayhteydestä, osan (mod p) voi jättää pois. Merkintä luetaan: "m on kongruentti n:n kanssa modulo p". Jatkossa tullaan käyttämään joitakin kongruenssien laskusääntöjä.

Todistus alkaa. Olkoon p alkuluku, p > 2. (Tapauksen p = 2 voi käsitellä erikseen.) Ensinnäkin, voidaan osoittaa, että kun p on alkuluku, niin

ja luku m on kullekin n:lle yksikäsitteinen. Ts. on kunta; kaikilla nollasta poikkeavilla alkioilla on 1-käsitteinen kertolaskuinverssi, kun p on alkuluku. (Tässä todistuksessa ei tarvitse tietää, mitä tai kunta tarkoittaa, vaikka oikeita käsitteitä käyttämällä tämäkin todistus voisi olla lyhyempi.)

Tutkitaan joukkoa S = {2, 3, ..., p - 2}, jossa on p - 3 lukua, siis parillinen määrä. Ensiksi osoitetaan, että mikään joukon S luvuista ei toteuta kongruenssia k² 1. Tämä nähdään kirjoittamalla kongruenssi muotoon (k-1)(k+1) = k² - 1 0, mistä seuraa, että

k - 1 0 tai k + 1 0. (**)

(Koska p | ab, p alkuluku p | a tai p | b.)

Mikään joukon S luvuista ei ehtoa (**) toteuta. (1 ja p-1 kelpaisivat.)

Joukon S luvut voidaan näinollen järjestää pareiksi siten että

Täten

Kertomalla edellinen puolittain p-1:llä saadaan

( p - 1 )! p - 1 -1

ja edelleen ( p - 1 )! + 1 0, eli (p-1)! + 1 on jaollinen p:llä ja väite on todistettu.

(Itseasiassa aluksi esitetty todistus toiseen suuntaan oli turha, sillä äskeinen vyörytys toimii tarvittavilta osin myös alhaalta ylös. Kun p:n ja (p-2)!:n suurin yhteinen tekijä on 1, p:n näkee alkuluvuksi.)