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

Lyhyt MathCheck-ohje (uuteen välilehteen)

Tässä tehtävässä harjoitellaan päättelemistä, jossa hyödynnetään sitä, että kohdemaailmassa on vain äärellinen määrä alkioita. Vaikka kokisit tehtävän lukuteoreettisen 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.

Johdanto

Aluksi kertaamme hieman aritmetiikkaa modulo p. Siinä kaikkia kokonaislukuja edustamaan riittävät 0, …, p − 1, koska tarvittaessa laskutoimituksen lopuksi lasketaan mod p.

Seuraava pätee moduloaritmetiikassa. Sitä tarvitaan laskuissa usein.

(0) Jos n ja k ovat kokonaislukuja ja p on positiivinen kokonaisluku, niin pk + n =_p n.

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

Lupa jakaa n pois

Seuraava tosiasia on laajalti tunnettu. Se on aika työläs todistaa, joten emme todista sitä tässä, vaan hyväksymme sen annettuna.

(1) Jos kahden kokonaisluvun tulo on jaollinen alkuluvulla p, niin jompi kumpi kerrottavista on jaollinen p:llä.

Todistamme seuraavan:

(2) Jos x ja y ovat välillä 0, …, p − 1, n ≠_p 0 ja nx =_p ny, niin x = y.

Käänteisarvo modulo alkuluku

Siis meillä on tietty määrä eri lukuja, jotka ovat väliltä, jossa on täsmälleen sama määrä eri vaihtoehtoja. Niinpä ne saavat jokaisen arvon em. väliltä kerran ja 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:

(3) Jos p on alkuluku ja n ≠_p 0, niin on olemassa täsmälleen yksi x ∈ {0, …, p − 1} siten, että nx =_p 1. Se ei ole 0.

Kutsumme tätä lukua käänteisarvoksi ja merkitsemme n⁻¹. Siis nn⁻¹ =_p 1. Koska kertolasku on vaihdannaista, pätee …n⁻¹n = nn⁻¹, joten myös n⁻¹n =_p 1.

Yritä todistaa, että (n⁻¹)⁻¹ = n!Tämä huutomerkki ei tarkoita kertomaa vaan on luonnollisella kielellä ilmaistun käskyn lopettava välimerkki. Tällainenkin monikäsitteisyys on tehtävien laatijoilla riesana. Määritelmän mukaan …(n⁻¹)⁻¹ on sellainen luku väliltä 1, …, p − 1, että n⁻¹ (n⁻¹)⁻¹ =_p 1. Tiedämme, että …n⁻¹n =_p 1 ja että …Käänteisarvo on yksikäsitteinen. Siksi (n⁻¹)⁻¹ = n.

Täydennä puuttuvat käänteisarvot, kun p = 13. Pääset helpommalla, jos hyödynnät yllä esiteltyjä käänteisarvon ominaisuuksia.

n	1	2	3	4	5	6	7	8	9	10	11	12
n⁻¹	only_no_yes_on ok_text Oikein! hide_expr f_nodes 1 1 =	7	9	end_of_answer arithmetic hide_expr f_nodes 1 10 =	8	end_of_answer arithmetic hide_expr f_nodes 1 11 =	end_of_answer arithmetic hide_expr f_nodes 1 2 =	end_of_answer arithmetic hide_expr f_nodes 1 5 =	end_of_answer arithmetic hide_expr f_nodes 1 3 =	4	end_of_answer arithmetic hide_expr f_nodes 1 6 =	12

tai

Reaalilukujen aritmetiikassa vastaluvun käänteisarvo on käänteisarvon vastaluku, eli (−x)⁻¹ = −x⁻¹. Päteeköhän sama aritmetiikassa modulo alkuluku? Kokeillaan! Olkoon 0 < n < p. Nolla jätettiin pois, koska sillä ei ole käänteisarvoa. Koska −n ei ole välillä 0, …, p − 1, luvun n vastalukuna ei käytetä sitä vaan lukua p − n, sillä se on oikealla välillä ja p − n =_p −n. Siis päteeköhän seuraava?

(4) (p − n)⁻¹ = p − n⁻¹

Ositus enintään neljän alkion joukoiksi

Seuraavaksi teemme tempun, joka saattaa vaikuttaa täysin hihasta vedetyltä, mutta myöhemmin paljastuu, että juuri se auttaa meitä pääsemään tavoitteeseen: ryhmittelemme luvut 0, …, p − 1 joukoiksi siten, että jokainen niistä kuuluu tasan yhteen joukkoon ja joukossa on enintään neljä erisuurta lukua. Annamme ensin määritelmän joukolle J_n, johon n kuuluu. Sitten todistamme, että ryhmittelyllämme on lupaamamme ominaisuudet.

Luku 0 muodostaa yksinään oman joukkonsa, jota merkitsemme J₀ = {0}. Jos 0 < n < p, niin otamme luvun n kanssa samaan joukkoon J_n luvut p − n, n⁻¹ ja p − n⁻¹. Siis J_n = {n, p − n, n⁻¹, p − n⁻¹}.

Todistamme, että jos 0 < n < p, niin J_n:n jokainen alkio on välillä 1, …, p − 1.

Alkiolle n se luvattiin oletuksessa.
p − n on tällä välillä, koska …Koska 0 < n < p, pätee p = p − 0 > p − n > p − p = 0.
n⁻¹ on tällä välillä, koska …(3) lupaa niin.
p − n⁻¹ on tällä välillä, koska …Juuri saatiin 0 < n⁻¹ < p. Siksi p = p − 0 > p − n⁻¹ > p − p = 0.

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

Alkioiden luettelointijärjestyksellä ei ole väliä.
Jos alkio esiintyy joukossa useasti, niin toistokerrat voi poistaa.

Jos esimerkiksi p = 13 ja n = 5, niin joukon J_n muut luvut ovat p − n = 13 − 5 = 8, n⁻¹ = 5⁻¹ = 8 ja p − n⁻¹ = 13 − 8 = 5. Siis J₅ = {5, 8, 8, 5} = {5, 8}. Huomaamme, että joukossa J_n voi olla vähemmän kuin 4 alkiota, koska esimerkiksi n ja p − n⁻¹ voivat olla yhtäsuuret.

Huomaamme, että J₃ = J₄. Alkiot on vain lueteltu eri järjestyksessä.

Muodostamistavan perusteella on ilmeistä, että jokainen n kuuluu ainakin joukkoon J_n, ja että kussakin J_n on enintään 4 alkiota. Olemme jo todistaneet, että missään J_n ei ole välin 0, …, p − 1 ulkopuolisia alkioita. Samalla tuli todistettua, että 0 ei kuulu mihinkään muuhun J_n kuin J₀. Mikään muu n kuin 0 ei kuulu J₀:aan, koska …Määritelmänsä mukaan J₀ = {0}.

Tarvitsee enää todistaa, että jokainen 1 ≤ i ≤ p − 1 kuuluu enintään yhteen joukkoon J_n, missä 1 ≤ n ≤ p − 1. Teemme sen olettamalla, että i kuuluu sekä joukkoon J_n että joukkoon J_m, missä 1 ≤ m ≤ p − 1, ja todistamme, että J_n = J_m. Todistamme ensin, että J_i = J_n. Koska i ∈ J_n, on neljä tapausta: i = n, i = p − n, i = n⁻¹ ja i = p − n⁻¹.

Jos i = n, niin väitteen 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ääritelmässä n:n paikalle p − n.
J_p − n = { ok_text Oikein! tree_compare p-n; , end_of_answer tree_compare p-(p-n); , end_of_answer tree_compare (p-n)^(-1); , end_of_answer tree_compare p-(p-n)^(-1); }
tai

Sieventämällä alkiot vaihtamatta niiden järjestystä saadaan
J_p − n = { ok_text Oikein! tree_compare p-n; , end_of_answer tree_compare n; , end_of_answer tree_compare p-n^(-1); , end_of_answer tree_compare n^(-1); } Se on sama joukko kuin J_n, mutta alkiot on lueteltu eri järjestyksessä.
tai
Ilmoita joukko alkiot sievennettyinä, mutta vaihtamatta niiden järjestystä.
J_n⁻¹ = { ok_text Oikein! tree_compare n^(-1); , end_of_answer tree_compare p-n^(-1); , end_of_answer tree_compare n; , end_of_answer tree_compare p-n; }
tai
Ilmoita joukko alkiot sievennettyinä, mutta vaihtamatta niiden järjestystä.
J_{p − n⁻¹} = { ok_text Oikein! tree_compare p-n^(-1); , end_of_answer tree_compare n^(-1); , end_of_answer tree_compare p-n; , end_of_answer tree_compare n; }
tai

Jokaiseen tuli täysin samat alkiot kuin joukossa J_n (vaikkakin eri järjestyksessä). Olemme osoittaneet, että kun 0 < i < p ja i ∈ 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.

Osituksen joukoissa on 4, 2 tai 1 alkiota

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

Seuraavaksi tutkimme tapauksia, joissa joukossa J_n on alle 4 alkiota.

Muistamme, että J₀ = {0}.
Koska 1 ⋅ 1 = 1, on 1⁻¹ = 1. Siksi J₁ = {1, p − 1, 1⁻¹, p − 1⁻¹} = {1, p − 1, 1, p − 1} = {1, p − 1}. Tässä joukossa on kaksi alkiota, koska …Muutoin pätisi 1 = p − 1 eli p = 2, vastoin oletusta p > 2.
Jos i² =_p −1, niin i(p − i) = ip − i² =_p −i² =_p 1, joten i⁻¹ = p − i. Silloin J_i = {i, p − i, i⁻¹, p − i⁻¹} = {i, p − i, p − i, p − (p − i)} = {i, p − i}. Huomaathan, että i on juuri sellainen luku, joista tavoitteemme on selvittää, onko niitä olemassa vai ei. Tässä joukossa on kaksi alkiota, koska …Muutoin pätisi p = 2i, vastoin sitä että p on pariton.

Seuraava tavoitteemme on todistaa, että kaikissa muissa joukoissa J_n on tasan 4 alkiota, eli että n, p − n, n⁻¹ ja p − n⁻¹ 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₀, J₁ tai J_i. Todistamme myös, että joukkoja J_i on enintään yksi.

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

Todistuksen viimeistely

Olemme valmiit loppuhuipennukseen.

Mitä teimme?

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 √−1 modulo p on olemassa. Näin saatiin √−1:n olemassaolo kytkettyä siihen, onko p muotoa 4k + 1 vai 4k + 3.

Suurin osa todistuksesta oli teknisiä yksityiskohtia, joilla osoitettiin, että ryhmittelyllä on tarvittavat ominaisuudet. Todistus venyi pitkäksi, koska todistimme myös asioita joiden normaalisti oletetaan tulleen tutuiksi lukuteorian perusopinnoissa ja koska olimme tavallista huolellisempia yksityiskohdissa. Tällä pyrittiin siihen, että todistus olisi ymmärrettävissä lukion pitkän matematiikan pohjalta.

Tapaus p = 2 on yksittäistapaus, joka oli helppo käsitellä erikseen.

	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.

	n on jaollinen p:llä.
	n ei ole jaollinen p:llä, joten (x − y) on.
	Kumpi tahansa voi olla jaollinen p:llä.

	2n on liian suuri.
	Aritmetiikka tapahtuu modulo p.
	p on pariton.

Teh­tä­vä: Ne­liö­juu­ri(−1) al­ku­lu­ku­kun­nis­sa

Joh­dan­to

Lu­pa ja­kaa n pois

Kään­teis­ar­vo mo­du­lo al­ku­lu­ku

Osi­tus enin­tään nel­jän al­kion jou­koik­si

Osi­tuk­sen jou­kois­sa on 4, 2 tai 1 al­kio­ta

To­dis­tuk­sen vii­meis­te­ly

Mi­tä teim­me?