Tehtävä:
Neliöjuuri(−1) alkulukukunnissa

Lyhyt MathCheck-ohje (uuteen välilehteen)

Tässä tehtävässä harjoitellaan päättelemistä. Päätel­mässä hyödynnetään sitä, että kohde­maailmassa on vain äärellinen määrä alkioita. Vaikka kokisit tehtävän luku­teoreettisen ajattelun vieraaksi, kannattaa silti jatkaa, sillä monessa kohdassa selvitään tavallisia lukuja koskevalla ajattelulla. Myös päättelyn perusjuoni kannattaa yrittää ymmärtää. Jotta se ei hukkuisi yksityiskohtien alle, se kerrataan lopussa.

Aluksi kertaamme hieman aritmetiikkaa modulo `p`. Siinä kaikkia kokonais­lukuja edustamaan riittävät `0, ..., p-1`, koska tarvittaessa lasku­toimituksen lopuksi lasketaan `mod p`.

Jos `p = 11`, niin paljonko on `n mod p`, kun `n` on annettu luku?
24 tai
20 tai
6 tai

Merkintä `n =_(p\ ) m` tarkoittaa, että `n mod p``=``m mod p`. Kuten koulussakin, `n = m` tarkoittaa, että `n` ja `m` ovat sama luku. Valitse oikea vaihtoehto.
Jos `n =_(p\ ) m` niin `n = m`, mutta ei välttämättä toisinpäin.
Jos `n = m` niin `n =_(p\ ) m`, mutta ei välttämättä toisinpäin.
`n =_(p\ ) m` jos ja vain jos `n = m`.
tai

Olkoon `p` alkuluku eli ykköstä suurempi kokonais­luku, jolla ei ole muita itseään pienempiä tekijöitä kuin ykkönen. Seuraaville alkuluvuille `p` on olemassa `0 <= n < p` siten, että `n^2 + 1` on jaollinen `p`:llä eli `n^2 + 1 =_(p\ ) 0` eli `n^2 =_(p\ ) -1`. Anna sellainen `n`.
2 tai
5 tai
13 tai
17 tai

Joillekin toisille alkuluvuille `p` sellaista `n` ei ole olemassa. Näin on esimerkiksi kun `p=7`. Sen osoittamiseksi laske `(n^2+1) mod 7` jokaiselle `0 <= n < 7`.
0 tai
1 tai
2 tai
3 tai
4 tai
5 tai
6 tai

Tavoitteemme on selvittää, mille alkuluvuille sellainen luku on ja mille ei ole olemassa. Sanomme pienintä sellaista lukua neliöjuuri miinus ykköseksi modulo `p`.

Seuraava tosi­asia on laajalti tunnettu ja aika työläs todistaa, joten emme todista sitä tässä, vaan hyväk­symme sen annettuna:

(1) Jos kahden kokonais­luvun tulo on jaollinen alku­luvulla `p`, niin jompi kumpi kerrottavista on jaollinen `p`:llä.


Todistamme ensin seuraavan:

(2) Jos `x` ja `y` ovat välillä `0, ..., p-1`, `n !=_(p\ ) 0` ja `nx =_(p\ ) ny`, niin `x = y`.

Muistathan, että yhteen-, vähennys- ja kertolaskuja voi tehdä aritmetiikassa modulo `p` aivan kuten kokonais­luvuilla? Vähentämällä yhtälön `nx =_(p\ ) ny` molemmilta puolilta `ny` saadaan `=_(p\ )` .
tai

Muunna vasen puoli muotoon jotain · (jotain ± jotain).
tai

Saatu yhtälö tarkoittaa, että sen vasen puoli on jaollinen `p`:llä. (1):n nojalla jompi kumpi kerrottavista on jaollinen `p`:llä. Ottaen huomioon mitä oletimme `n`:stä, yksi seuraavista pätee, mikä?
`n` on jaollinen `p`:llä.
`n` ei ole jaollinen `p`:llä, joten `(x-y)` on.
Kumpi tahansa voi olla jaollinen `p`:llä.
tai

Koska `x` ja `y` ovat em. väliltä, `<=``x-y``<=` . (Valitse mahdollisimman tiukat rajat. Toisen rajan saat kun valitset suurimman `x` ja pienimmän `y` jotka ovat em. välillä, ja toiselle rajalle päinvastoin.)
tai

Kun tämä yhdistetään aikaisempaan jaollisuustietoon, saadaan `x-y =` , joten (2) on todistettu.
tai


(2):n nojalla, jos `n !=_(p\ ) 0`, niin `0n mod p`, `1n mod p`, `2n mod p`, …, `(p-1)n mod p` ovat eri lukuja. Niitä on kappaletta ja ne saavat arvonsa väliltä , …, , jossa on eri lukua. Niinpä ne saavat jokaisen arvon ym. väliltä. Koska ne ovat eri lukuja, ne saavat kunkin arvonsa vain kerran. Luku 1 on em. välillä, joten ne saavat arvokseen ykkösen yhden ja vain yhden kerran. Koska `0n = 0`, ei voi olla `0n mod p = 1`. Olemme osoittaneet seuraavan:
tai

(3) Jos `p` on alkuluku ja `n !=_(p\ ) 0`, niin on olemassa tasan yksi `x in {0, ..., p-1}` siten, että `nx =_(p\ ) 1`. Se ei ole 0.

Kutsumme tätä lukua käänteisarvoksi ja merkitsemme `n^(-1)`. Siis `n n^(-1) =_(p\ ) 1`. Määritelmän mukaan `(n^(-1))^(-1)` on sellainen luku, että `n^(-1) (n^(-1))^(-1) =_(p\ ) 1`. Koska `n^(-1) n``=``n n^(-1)`, on `n^(-1) n =_(p\ ) 1`. Siksi `(n^(-1))^(-1) = n`.

Täydennä puuttuvat käänteisarvot, kun `p=13`. Pääset helpommalla, jos hyödynnät yllä esiteltyjä käänteisarvon ominaisuuksia.
`n`12345 6789101112
`n^(-1)` 79 8 4 12
tai

Seuraavaksi teemme tempun, joka saattaa vaikuttaa täysin hihasta vedetyltä, mutta myöhemmin paljastuu, että juuri se auttaa meitä pääsemään tavoitteeseen: ryhmit­telemme luvut `0, ..., p-1` joukoiksi siten, että jokainen niistä kuuluu tasan yhteen joukkoon ja joukossa on enintään neljä erisuurta lukua. Luku 0 muodostaa yksinään oman joukkonsa, jota merkitsemme `J_0 = {0}`. Jos `0 < n < p`, niin otamme luvun `n` kanssa samaan joukkoon `J_n` luvut `p-n`, `n^(-1)` ja `p-n^(-1)`. Siis `J_n``=``{n, p-n, n^(-1), p-n^(-1)}`. Koska `0 < n < p`, pätee `p``=``p-0``>``p-n``>``p-p``=``0`, joten `p-n` on oikealla välillä.

Matematiikan joukoilla on kaksi tärkeää ominaisuutta, joita tulemme tarvitsemaan:

Jos esim. `p=13` ja `n=5`, niin joukon `J_n` muut luvut ovat `p-n``=``13-5``=``8`, `n^(-1)``=``5^(-1)``=``8` ja `p-n^(-1)``=``13-8``=``5`. Siis `J_5``=``{5, 8, 8, 5}``=``{5, 8}`. Huomaamme, että joukossa `J_n` voi olla vähemmän kuin 4 alkiota, koska esim. `n` ja `p-n^(-1)` voivat olla yhtä­suuret.

Kun `p=13`, luettele seuraavat joukot järjestyksessä `{n, p-n, n^(-1), p-n^(-1)}`.
`J_1 = {` , , , `}` tai
`J_2 = {` , , , `}` tai
`J_3 = {` , , , `}` tai
`J_4 = {` , , , `}` tai

Huomaamme, että `J_3 = J_4`, alkiot on vain lueteltu eri järjestyksessä.

Meidän on todistettava, että joukoilla `J_n` ovat ne ominaisuudet jotka lupasimme niillä olevan. Muodostamis­tavan perusteella on ilmeistä, että kussakin `J_n` on enintään 4 alkiota. Jokainen `n` kuuluu ainakin joukkoon `J_n`. Tarvitse enää todistaa, että jokainen luku kuuluu enintään yhteen joukkoon.

Ensin osoitamme, että 0 ei kuulu mihinkään muuhun `J_n`. Se tarkoittaa, että oletamme `0 < n < p`, ja meidän on osoitettava 0 erisuureksi joukon `J_n` jokaisen alkion kanssa.

`n`:
Jo lähtökohdissa sanottiin, että `0 < n`.
`p-n`:
Lähtökohdissa sanottiin, että `n < p`, joten `p-n``>``0`.
`n^(-1)`:
(3) kertoo, että `0 != n^(-1)`.
`p-n^(-1)`:
(3):n mukaan `n^(-1) < p`, joten `p-n^(-1) > 0`.

Vielä tarvitsee todistaa, että kukin luku väliltä `1, ..., p-1` kuuluu vain yhteen joukkoon. Teemme sen olettamalla, että `i` kuuluu sekä joukkoon `J_n` että joukkoon `J_m`, ja todistamme, että `J_n = J_m`. Koska `J_0` sisältää vain nollan, pätee `n != 0` ja `m != 0`. Todistamme ensin, että `J_i = J_n`. Koska `i in J_n`, on neljä tapausta: `i = n`, `i = p-n`, `i = n^(-1)` ja `i = p-n^(-1)`.

Jos `i=n`, niin tuloksen `J_i = J_n` todistukseksi riittää huomauttaa, että tavoite on lähes valmiina lähtö­kohdissa. Se tehdään sanomalla, että tapaus on triviaali.

Päästäksemme alkuun tapauksen `i = p-n` kanssa, esitä `J_(p-n)` niin että et vaihda alkioiden järjestystä etkä sievennä mitään. Siis ainoastaan sijoita `J_n`:n määri­telmässä `n`:n paikalle `p-n`.
`J_(p-n)``=``{` , , , `}`
tai

Ehkä huomaat, että muuten saisimme helposti sievennettyä `J_(p-n)`:n samaksi kuin `J_n`, mutta tarvit­semme tietoa `(p-n)^(-1)``=``p-n^(-1)`, kun `0 < n < p`. Niinpä seuraavaksi todistamme sen. Sievennä `(p-n)(p-n^(-1)) = p(``)``+ n n^(-1)``=_(p\ )` . Tämä todistaa, että on luvun `p-n` käänteisarvo, eli `(p-n)^(-1)``=``p-n^(-1)`.
tai

Esitä seuraavat joukot siten, että alkiot ovat alku­peräisessä järjestyksessä mutta sievennettyinä.
`J_(p-n) = {` , , , `}`
tai

`J_(n^(-1)) = {` , , , `}`
tai

`J_(p-n^(-1)) = {` , , , `}`
tai

Jokaiseen tuli täysin samat alkiot kuin joukossa `J_n` (vaikkakin eri järjestyksessä). Olemme osoittaneet, että kun `0 < i < p` ja `i in J_n`, niin `J_i = J_n`.

Samasta syystä pätee `J_i = J_m`. Ne yhdistämällä saadaan `J_n = J_i = J_m`. Nyt on osoitettu, että myös muut tutkittavan välin luvut kuin 0 kuuluvat vain yhteen joukkoon.


Tulemme jatkossa tarvitsemaan oletusta `p > 2`. Siksi tapaus `p = 2` täytyy hoitaa erikseen. Mutta mehän olemme jo hoitaneet sen, katso edeltä! Kun `p = 2`, onko olemassa sellaista `0 <= n < p`, että `n^2 =_(p\ ) -1`? Kirjoita ei tai sellainen luku. ,
tai

Tästä eteenpäin oletamme, että `p > 2`. Koska `p` on alkuluku, siitä seuraa, että `p` on pariton.

Muistamme, että `J_0 = {0}`. Koska `1 * 1 = 1` ja `(p-1)(p-1)``=``p(p-2)+1``=_(p\ ) 1`, on `1 = 1^(-1)` ja `p-1``=``(p-1)^(-1)`, joten `J_1``=``{1, p-1}`. Jos `i^2``=_(p\ )``-1`, niin `i(p-i)``=``ip - i^2``=_(p\ )``1`, joten `i^(-1)``=``p-i`. Silloin `J_i``=``{i, p-i}`. Huomaathan, että `i` on juuri sellainen luku, joista tavoitteemme on selvittää, onko niitä olemassa vai ei.

Seuraava tavoit­teemme on todistaa, että kaikissa muissa joukoissa `J_n` on tasan 4 alkiota, eli että `n`, `p-n`, `n^(-1)` ja `p-n^(-1)` ovat kaikki keskenään erisuuria. Teemme oletuksia, että kaksi niistä onkin yhtäsuuria, ja todistamme, että päädytään mahdottomuuteen tai johonkin em. joukoista `J_0`, `J_1` tai `J_i`.

Jos olisi `n = p-n`, niin olisi `p =` , mikä on mahdotonta, koska
`2n` on liian suuri.
Aritmetiikka tapahtuu modulo `p`.
`p` on pariton.
tai

Jos `n = n^(-1)`, niin `n^2``=``n n^(-1)``=_(p\ )` . Se tarkoittaa, että `n^2-1``=_(p\ )` , eli `n^2-1` on jaollinen `p`:llä. Koska `n^2-1 = (n-1)(n+1)` ja koska `0 <= n < p`, (1):n nojalla `n` on joko tai (ilmoita pienempi ensin). Tällaisia joukkoja `J_n` on siis vain `J_1`.
tai

Siirrymme tapaukseen `n = p-n^(-1)`. Tee ensin yksi tai kaksi sievennys­askelta tavallisella yhtäsuuruudella, ja sitten yksi sievennys­askel modulo `p`. Laatikossa on vihjeenä hieman alkua. Kone tulkitsee `n^(-1)` normaalisti eikä käänteis­arvona modulo `p`, joten virhe­ilmoituksissa esiintyvät luvut voivat olla outoja. Kuitenkin, kun olet saanut tuloksen oikein tällä tulkinnalla, se on oikein myös käänteis­arvona modulo `p`.
`n^2 + 1 =` `=_(p\ )` .
tai

Tämä tarkoittaa, että `n^2 + 1` on jaollinen `p`:llä. Seuraavaksi todistamme, että on toinenkin luku, jolle ko. lauseke on jaollinen `p`:llä, mutta ei enää kolmatta. Olkoon siis `m^2 + 1` jaollinen `p`:llä. Silloin myös
`m^2 + 1 - (n^2 + 1)``=` (sievennä kerto­laskuksi) on jaollinen `p`:llä. Siksi `m = n` tai `m =` .
tai

Termejä puolelta toiselle siirtelemällä nähdään, että tapaus `p-n = n^(-1)` on sama kuin `n=` , ja `p-n = p-n^(-1)` on sama kuin `n=` , jotka on jo käsitelty. Tapaus `n^(-1) = p-n^(-1)` on mahdoton samasta syystä kuin `n=p-n`. Olemme tutkineet kaikki tapaukset, joissa kaksi erikseen ilmoitettua `J_n`:n alkiota ovatkin yhtä­suuret.
tai

Olemme saaneet valmiiksi todistuksen, että kaikki muut `J_n` sisältävät neljä alkiota, paitsi `J_0` jossa on yksi alkio; `J_1` jossa on kaksi alkiota; sekä korkeintaan yksi `J_i`, missä `i^2 + 1` on jaollinen `p`:llä. Jos `J_i` on olemassa, niin siinä on kaksi alkiota.


Olemme valmiit loppuhuipennukseen.

Pariton luku jättää neljällä jaettaessa jakojäännökseksi joko 1 tai 3. Siksi pariton `p` on joko muotoa `4k+1` tai muotoa `4k+3`, missä `k in NN`. Koska jokainen luku väliltä `0, ..., p-1` kuuluu tasan yhteen joukkoon `J_n` ja muita lukuja niissä ei ole, on joukkojen `J_n` kokojen summa tasan .
tai

Olkoon `j` niiden joukkojen `J_n` määrä, joissa on tasan 4 alkiota. Jos edellä mainittua joukkoa `J_i` ei ole olemassa, on joukkojen `J_n` kokojen summa , joka on muotoa . Muussa tapauksessa summa on , joka on muotoa . Niinpä sellainen `n`, että `n^2 + 1` on jaollinen `p`:llä, on olemassa jos ja vain jos `p=2` tai `p mod 4 = 1`.
tai


Todistuksen pääjuoni tapauksessa `p > 2` oli siis ryhmitellä luvut `0, ..., p-1` yhdeksi yhden alkion joukoksi, yhdeksi kahden alkion joukoksi, nollaksi tai useammaksi neljän alkion joukoksi sekä mahdollisesti vielä yhdeksi kahden alkion joukoksi siten, että viimeksi mainittu joukko on olemassa jos ja vain jos neliöjuuri(−1) modulo `p` on olemassa. Näin saatiin neliöjuuri(−1):n olemassaolo kytkettyä siihen, onko `p` muotoa `4k+1` vai `4k+3`.

Suurin osa todistuksesta oli teknisiä yksityis­kohtia, joilla osoitettiin, että ryhmittelyllä on tarvittavat ominaisuudet. Todistus venyi pitkäksi, koska todistimme myös asioita joiden normaalisti oletetaan tulleen tutuiksi lukuteorian perus­opinnoissa ja koska olimme tavallista huolel­lisempia yksityis­kohdissa. Tällä pyrittiin siihen, että todistus olisi ymmärrettävissä lukion pitkän matema­tiikan pohjalta.

Tapaus `p = 2` on yksittäis­tapaus, joka oli helppo käsitellä erikseen.