Neliönjäännökset

Tutkitaan kokonaislukuja modulo 3. Huomataan, että 0² ≡ 0 (mod 3), 1² ≡ 1 (mod 3)ja2² ≡1 (mod 3). Mikään näistä neliöistä ei ole2 (mod 3). Tästä oikeastaan

seuraa, että yhtälöllä𝑥² ≡2 (mod 3) ei ole ratkaisua:

Valitaan mielivaltainen kokonaisluku𝑥. Tiedetään, että𝑥on joko0,1tai2modulo3. Jos𝑥≡0 (mod 3), niin neliöimällä yhtälö saadaan𝑥² ≡0² ≡0 (mod 3). Vastaavasti muissa tapauksissa saadaan 𝑥² ≡1² ≡1 (mod 3) ja 𝑥² ≡2² ≡1 (mod 3).

Mitä tapahtuu, jos 3 korvataan jollain muulla alkuluvulla?³⁸ Määritelmä

Olkoon 𝑝 alkuluku. Sanotaan, että kokonaisluku𝑎 on neliönjäännös modulo 𝑝, jos on olemassa kokonaisluku 𝑥, jolla 𝑥² ≡ 𝑎 (mod𝑝) ja 𝑝 - 𝑎. Vastaa-vasti sanotaan, että 𝑎 on neliönepäjäännös modulo 𝑝, jos 𝑥² ̸≡ 𝑎 (mod𝑝) kaikilla 𝑥 ja 𝑝 - 𝑎. Luvut 𝑎 ≡ 0 (mod𝑝) eivät ole neliönjäännöksiä eivätkä neliönepäjäännöksiä.

Esimerkki

Luku 1on neliönjäännös modulo 3, ja luku 2 on neliönepäjäännös modulo3. Kuinka monta neliönjäännöstä tai neliönepäjäännöstä on modulo𝑝? Tehdään pieni lista:

• Jos 𝑝= 2, on 1 neliönjäännös: 1. Neliönepäjäännöksiä on 0 kappaletta.

• Jos 𝑝= 3, on 1 neliönjäännös: 1. Neliönepäjäännöksiä on 1 kappale.

• Jos 𝑝= 5, on 2 neliönjäännöstä: 1 ja 4. Neliönepäjäännöksiä on2 kappaletta.

• Jos𝑝= 7, on 3neliönjäännöstä:1,2ja4. Neliönepäjäännöksiä on3kappaletta.

• Jos 𝑝 = 11, on 5 neliönjäännöstä: 1, 3, 4, 5 ja 9. Neliönepäjäännöksiä on 5 kappaletta.

37Muistan joskus nähneeni tehtävän, jossa tutkittiin ainakin viittä eri moduloa, joista viimeinen oli37. Silloin ajattelin, että ratkaisu oli aivan mahdoton, mutta ratkaisulle on selvä motivaatio:

Luku37 on alkuluku, joten Fermat’n pienen lauseen nojalla eksponenttifunktiot ovat jaksollisia modulo37jaksolla36. Luvulla36on vain pieniä alkutekijöitä, joten se kommunikoi hyvin muiden kongruenssiehtojen kanssa.

38Mielivaltainen kokonaislukumodulo voidaan palauttaa kiinalaisella jäännöslauseella alkuluvun potensseihin, ja tämä ei ole paljoa vaikeampi tapaus kuin jos modulo olisi alkuluku (katso Lukuteorian lisätehtävät -luvun toisen tehtävän kommentti).

Vaikuttaisi siltä, että neliönjäännöksiä ja -epäjäännöksiä on aina sama määrä, eli

𝑝−1

2 (paitsi kun 𝑝= 2).

Lemma

Olkoon 𝑝pariton alkuluku. Luvuista 1,2, . . . , 𝑝−1täsmälleen ^𝑝−1₂ ovat neliön-jäännöksiä modulo 𝑝.

Neliönjäännökset saadaan listaamalla 1²,2²,3², . . . ,(𝑝−1)². Näissä tulisi olla ^𝑝−1₂ eri lukua.

Valitaan 𝑝= 13. Tällöin luvut 1²,2², . . . ,12² ovat

1,4,9,3,12,10,10,12,3,9,4,1 (mod 13).

Säännönmukaisuus on selvä: ensimmäiset ^𝑝−1₂ lukua ovat eri lukuja, ja sitten samat luvut toistuvat käänteisessä järjestyksessä. Loppuosan toistuminen johtuu yksinker-taisesti yhtälöstä𝑥² ≡(𝑝−𝑥)² (mod 𝑝), mikä seuraa suoralla laskulla:

(𝑝−𝑥)² =𝑝²−2𝑝𝑥+𝑥² ≡𝑥² (mod 𝑝).

Entä alkuosan käyttäytyminen?

Haluamme osoittaa, että 𝑎² ̸≡ 𝑏² (mod 𝑝), kun 1 ≤ 𝑎, 𝑏 ≤ ^𝑝−1₂ ja 𝑎 ja 𝑏 ovat erisuuria. Oletetaan, että olisikin𝑎² ≡𝑏² (mod 𝑝). Tällöin 𝑝|𝑎²−𝑏² = (𝑎−𝑏)(𝑎+𝑏). Eukleideen lemman nojalla joko𝑝|𝑎−𝑏tai𝑝|𝑎+𝑏. Kumpikaan näistä ei ole mahdollinen vaihtoehto, koska 1≤𝑎, 𝑏≤ ^𝑝−1₂ ja 𝑎 ̸=𝑏. Olemme valmiit.

Tässä on pari yksinkertaista esimerkkiä neliönjäännösten sovelluksesta yhtälöiden kokonaislukuratkaisujen etsimiseen. Ensimmäinen on vanha valmennustehtävä.

Tehtävä

Määritä yhtälön 𝑥²−3𝑦² = 17 kaikki kokonaislukuratkaisut.

Kokeilemalla pieniä lukujen 𝑥 ja 𝑦 arvoja ei löydetä ratkaisuja. Syy tälle on seuraava: Jos (𝑥, 𝑦)on ratkaisu, niin 𝑥²−3𝑦² = 17, ja täten 𝑥²−3𝑦² ≡17 (mod 3). Tästä seuraa𝑥² ≡2 (mod 3), mikä on mahdotonta. Ratkaisuja ei siis ole.

Todistus perustuu siihen, että halutulla yhtälöllä ei ole ratkaisuja modulo 3. Vastaavaa ideaa voi hyödyntää yleisemminkin korvaamalla luvun 3 jollain muulla kokonaisluvulla. Tässä on toinen samantyylinen esimerkki.

Tehtävä

Määritä yhtälön 𝑥²+𝑦²+𝑧² = 3996kaikki kokonaislukuratkaisut.

Koska 𝑎² ≥ 0 kaikilla 𝑎, tulee kaikkien luvuista 𝑥, 𝑦 ja 𝑧 olla enintään √ 3996, koska muuten vasen puoli olisi suurempi kuin oikea. Siispä mahdollisia kandidaatteja luvuille 𝑥, 𝑦 ja 𝑧 on vain äärellisen monta, eli ne voisi periaatteessa käydä läpi.

Vaihtoehtoja on kuitenkin liikaa käsin kokeiltavaksi, joten mietitään jotain muuta.

Voidaan kokeilla moduloita. Yhtälön tarkkaileminen modulo 2 tai modulo 3 ei tunnu antavan mitään hyödyllistä, mutta modulo 4 saadaan jotain: koska luvut 0²,1²,2² ja 3² ovat 0,1,0,1 modulo 4, pätee 𝑎² ≡ 0 (mod 4) tai 𝑎² ≡ 1 (mod 4) kaikilla kokonaisluvuilla𝑎. On neljä mahdollista tapausta:

1. Kaikki kolme lukua 𝑥, 𝑦 ja 𝑧 ovat sellaisia, joiden neliö on 0 (mod 4). Tällöin 𝑥² +𝑦²+𝑧² ≡0 (mod 4). oikea puoli on pienentynyt. Tämä on edistystä.

Modulo 4 ei juurikaan auta enää: saamme, että 𝑎, 𝑏ja 𝑐 ovat parittomia, mutta se siitä. Voidaan kokeilla muita moduloita. Modulo 8 sattuu toimimaan: voidaan tarkistaa, että 𝑥² ≡ 0,1 tai 4 (mod 8). Ei ole mahdollista valita kolmea lukua joukosta {0,1,4} niin, että niiden summa olisi 999 ≡ 7 (mod 8). Tämän takia ratkaisuja ei ole.

Onko mitään nopeaa tapaa määrittää, onko jokin tietty kokonaisluku neliönjäännös modulo 𝑝? Yksi tapa on listata neliöt 1²,2², . . . ,(︀𝑝−1

2

)︀2

, mutta on myös nopeampi menetelmä. Esitetään teoriaa, jonka sovelluksena saadaan tämä nopeampi menetelmä sekä muita tuloksia.

Määritelmä

Olkoon 𝑎 kokonaisluku, ja olkoon 𝑝alkuluku. Määritellään Legendren symboli (︁𝑎

𝑝

)︁ seuraavasti: jos 𝑎 on neliönjäännös modulo 𝑝, niin (︁

𝑎 𝑝

)︁

= 1, jos 𝑎 on neliönepäjäännös modulo 𝑝, niin (︁

𝑎

Merkintä muistuttaa ikävästi jakolaskua, mutta kontekstista voi päätellä, mitä tarkoitetaan.

2. Kahden neliönjäännöksen tulo on neliönjäännös: jos 𝑥² ≡𝑎 (mod 𝑝) ja 𝑦² ≡𝑏 (mod 𝑝), niin(𝑥𝑦)² ≡𝑎𝑏 (mod 𝑝).

Seuraava lemma yleistää jälkimmäistä huomiota.

Lemma

Olkoon 𝑝 alkuluku. Kaikilla kokonaisluvuilla 𝑎 ja 𝑏 pätee (︂𝑎

Tulosta voi tavallaan ajatella tulon merkkisääntönä. Reaaliluvuissa luku on neliö jos ja vain jos se on epänegatiivinen. Kahden neliön tulo on neliö, neliö kerrottuna epäneliöllä on epäneliö, ja kahden epäneliön luvun tulo on neliö. Lemman tulos todistaa saman kokonaisluvuille modulo𝑝.

Lemma selvästi pätee, jos 𝑎≡0 (mod 𝑝)tai𝑏 ≡0 (mod 𝑝), koska tällöin saadaan eli merkkivaihtoehto(+,+).

Tutkitaan seuraavana tapaus (−,+). Oletetaan siis, että 𝑎 on neliönepäjäännös ja 𝑏 on neliönjäännös, ja yritetään todistaa, että 𝑎𝑏 on neliönepäjäännös. Tehdään vastaoletus: luku 𝑎𝑏 on neliönjäännös modulo 𝑝. Kirjoitetaan 𝑥² ≡ 𝑏 (mod 𝑝) ja 𝑦² ≡𝑎𝑏 (mod𝑝). Koska 𝑏̸≡0 (mod 𝑝), on luvuilla𝑏 ja 𝑥 käänteisluvut 𝑏⁻¹ ja 𝑥⁻¹ modulo𝑝. Nyt

𝑎≡𝑎𝑏·𝑏⁻¹ ≡𝑦²·(𝑥⁻¹)² ≡(𝑦𝑥⁻¹)² (mod 𝑝), eli𝑎 onkin neliönjäännös modulo 𝑝, mikä on ristiriita.

Merkkivaihtoehto (+,−) seuraa symmetrian nojalla.

Jäljellä on vaikein tapaus (−,−), eli se, että kahden neliönepäjäännöksen tulo on neliönjäännös. Idea todistuksessa on valita jokin neliönepäjäännös ja todistaa, ettei sitä voi esittää kahden neliönepäjäännöksen tulona. Tämä tehdään laskemalla tietynlaisten parien lukumääriä.

Valitaan jokin neliönepäjäännös 𝑐. Kuinka monta paria sellaista paria (𝑎, 𝑏) on, joilla 𝑎𝑏≡𝑐 (mod𝑝)? Koska 𝑐̸≡0 (mod 𝑝), niin 𝑎, 𝑏̸≡0 (mod 𝑝). Jokaista luvun 𝑎 vaihtoehtoa 1,2, . . . , 𝑝−1 vastaa yksikäsitteinen𝑏, nimittäin 𝑎⁻¹𝑐. Siis yhtälöllä 𝑎𝑏≡𝑐 (mod 𝑝) on täsmälleen 𝑝−1ratkaisua.

Mitä näistä ratkaisuista voidaan sanoa? Jos 𝑎on neliönjäännös (tällaisia ratkaisuja on ^𝑝−1₂ kappaletta), niin𝑏:n tulee olla neliönepäjäännös. Jos taas𝑏 on neliönjäännös (tällaisia ratkaisuja on myös ^𝑝−1₂ kappaletta), niin 𝑎 on neliönepäjäännös. Nämä tapaukset käsittelevät kaikki 𝑝−1 ratkaisua. Jokaisessa näistä ratkaisuista tasan yksi luvuista 𝑎 ja 𝑏 on neliönjäännös, mikä todistaa väitteen: lukua𝑐 ei voi esittää kahden neliönepäjäännöksen tulona.

Seuraavaksi esitetään ilman todistuksia pari neliönjäännöksiin liittyvää tulosta.

Todistuksista kiinnostuneelle lukijalle suositellaan valmennuksen sivuilta löytyvää Esa Vesalaisen materiaalia Lyhyt johdatus alkeelliseen lukuteoriaan. Materiaalissa esitetään myös erilainen todistus edelliselle lemmalle.³⁹

Lemma

Olkoon𝑝 pariton alkuluku. Tällöin −1 on neliönjäännös modulo 𝑝 täsmälleen silloin, kun 𝑝≡1 (mod 4).

Lemma

Olkoon 𝑝 pariton alkuluku. Tällöin 2 on neliönjäännös modulo 𝑝täsmälleen silloin, kun 𝑝≡1 (mod 8) tai 𝑝≡7 (mod 8).

Edelliset kaksi lemmaa toimivat täydennyksinä seuraavalle tulokselle. Todistusta ei esitetä tässä, mutta myös tämän väitteen todistus on esitetty Vesalaisen materiaalissa.

Lause (Neliönjäännösten resiprookkilaki)

Olkoot 𝑝 ja 𝑞 parittomia alkulukuja. Jos vähintään toinen luvuista 𝑝 ja 𝑞 on 1 (mod 4), niin (︁

Esitetään nyt aiemmin luvattu menetelmä, jonka avulla pystyy laskemaan arvon (︁𝑎

𝑝

)︁nopeasti. Tehdään tämä esimerkin kautta.

Esimerkki Lasketaan (︀₁₀₁₀

2017

)︀ (ei ole ilmeistä, että 2017on alkuluku, mutta näin on).

Hajotetaan1010alkutekijöihin:1010 = 2·5·101. Käyttämällä ”tulon merkkisääntöä”

saadaan (︂

Lasketaan jokainen termi yksitellen. Ensimmäiseen termiin ei voida käyttää re-siprookkilakia (koska2 ei ole pariton alkuluku), mutta voidaan käyttää toista täy-dentävää tulosta: pätee2017 ≡1 (mod 8), joten 2 on neliönjäännös modulo 2017. Ensimmäinen termi on siis +1.

39Pidän Vesalaisen esittämää todistusta Legendren symbolin tulon merkkisäännölle parempana, koska se on luonnollinen osa neliönjäännösten teoriaa ja koska vastaavilla menetelmillä saadaan osoitettua muun muassa se, että −1 on neliönjäännös modulo 𝑝jos ja vain jos 𝑝≡ 1 (mod 4).

Esittämäni todistus parien lukumääriä laskemalla on kuitenkin mielestäni helpompi keksiä itse, minkä vuoksi esitin tämän ratkaisun.

Toiseen termiin voidaan soveltaa resiprookkilakia, eli saadaan

Viimeiseen termiin voidaan vastaavasti soveltaa resiprookkilakia:

(︂ 101

Ensimmäinen termi on+1ensimmäisen täydentävän lemman nojalla, ja toinen termi on−1 resiprookkilain avulla.

Keräämällä tulokset yhteen saadaan, että (︀₁₀₁₀

2017

)︀= 1.

Huomaa, että neliönjäännösten resiprookkilaki ja sen täydennystulokset antavat tavan laskea symbolin(︁

𝑎 𝑝

)︁ arvon millä tahansa alkuluvulla𝑝 ja kokonaisluvulla 𝑎. Tämän luvun viimeinen tehtävä demonstroi tätä ideaa.

Tehtävä

Olkoon 𝑎 kokonaisluku. Oletetaan, että 𝑎 ei ole neliöluku. Osoita, että on olemassa äärettömän monta alkulukua 𝑝, joilla𝑎 on neliönepäjäännös modulo 𝑝.

Ehto siitä, ettei 𝑎 ole neliöluku, on selvästi välttämätön väitteen pätevyydelle.

Mistä aloitetaan? Tutkitaan jotain yksinkertaista tapausta, vaikkapa 𝑎 = −1. Tällöin halutaan, että äärettömän monella alkuluvulla 𝑝pätee𝑝≡3 (mod 4). Tämä väite pätee ja on erikoistapaus erittäin tunnetusta Dirichlet’n lauseesta. Lauseen tulos on hyvin uskottavan kuuloinen, ja tulos on hyvä pitää mielessä.

Lause (Dirichlet’n lause)

Olkoot 𝑎 ja 𝑏 yhteistekijättömiä positiivisia kokonaislukuja. On olemassa äärettömän monta alkulukua 𝑝, joilla 𝑝≡𝑎 (mod 𝑏).

Tämä ratkaisee tapauksen 𝑎 =−1. Myös tapaus 𝑎= 2ratkeaa tämän lauseen ja täydennystuloksen avulla.

Edetään hieman vaikeampaan tapaukseen: olkoon 𝑎 = 𝑞 jollain alkuluvulla 𝑞. Voidaan olettaa, että 𝑞 >2. Halutaan

(︂𝑞 𝑝

)︂

=−1.

Käytetään neliönjäännösten resiprookkilakia. Yritetään valita𝑝≡1 (mod 4), jolloin resiprookkilakia käytettäessä ei synny etumerkkiä−. Näillä 𝑝 halutaan

(︂𝑝 𝑞

)︂

=−1.

Tämä onnistuu: Koska 𝑞 >2, on olemassa neliönepäjäännös𝑎 (mod 𝑞). Valitaan 𝑝 niin, että𝑝≡𝑎 (mod 𝑞)ja𝑝≡1 (mod 4). Nämä ehdot voidaan kirjoittaa kiinalaisen jäännöslauseen avulla muodossa 𝑝 ≡ 𝑏 (mod 4𝑞) sopivalla 𝑏. Pätee syt(𝑏,4𝑞) = 1 (miksi?), joten Dirichlet’n lause todistaa väitteen.

Yritetään sitten ratkaista yleinen tapaus. Oletetaan yksinkertaisuuden vuoksi ensiksi, että𝑎 >0 ja että 𝑎 on pariton. Kirjoitetaan 𝑎=𝑞₁^𝑒1𝑞₂^𝑒2· · ·𝑞^𝑒_𝑛^𝑛, missä𝑞_𝑖 ovat vain äärellisen monta 𝑝). Nämä termit voidaan unohtaa. Jos 𝑒_𝑖 on pariton, niin (︁_𝑞𝑒𝑖

Nyt vaikuttaa hyvältä tilaisuudelta käyttää resiprookkilakia. Kuten alkulukutapauk-sessa oletetaan nytkin, että 𝑝≡1 (mod 4). Saadaan

(︂𝑟1

Haluamme siis valita luvun 𝑝 niin, että tämä tulo on −1. Naiivi tapa on yrit-tää valita 𝑝 niin, että ensimmäinen termi on −1 ja loput termit ovat +1. Tämä myös onnistuu. Alkuluvut 𝑟𝑖 ovat oletuksen nojalla parittomia, joten on olemassa neliönepäjäännös 𝑡 (mod 𝑟₁). Valitaan 𝑝 seuraavasti:

• 𝑝≡𝑡 (mod 𝑟₁). Näin saadaan ensimmäisestä termistä −1.

• 𝑝≡1 (mod 𝑟_𝑖) kaikilla 𝑖≥2. Näin saadaan muista termeistä +1.

• 𝑝≡1 (mod 4). Tätä ehtoa käytettiin resiprookkilakia sovellettaessa.

Ehdot voidaan yhdistää kiinalaisella jäännöslauseella, eli saadaan 𝑝≡𝑠 (mod 𝑚). Jälleen pätee syt(𝑠, 𝑚) = 1(miksi?), joten Dirichlet’n lause todistaa väitteen. (Missä kohtaa käytettiin tietoa siitä, että𝑎 ei ole neliöluku?)

Oletimme, että 𝑎 > 0 ja että 𝑎 on pariton. Muut tapaukset voidaan kuitenkin käsitellä vastaavalla tavalla (tarkastelu on hieman vaivalloinen, muttei mitenkään vaikea, joten se sivuutetaan).

Huomaa, että vastaavalla tavalla saadaan luotua äärettömän monta alkulukua 𝑝, joilla 𝑎 on neliönjäännös modulo 𝑝. Tämä ongelma on yksityiskohtien puolesta helpompi kuin edellä esitetty.⁴⁰

40Tämän ongelman voi ratkaista myös toisella tavalla tutkimalla niitä𝑝, jotka jakavat jonkin polynomin𝑃(𝑥) =𝑥²−𝑎arvoista kokonaislukupisteessä (katso Lukuteorian lisätehtävät -luvun toisen tehtävän kommentti, erityisesti Schurin lause).

10 Primitiivijuuret (Lukuteoria)

Tässä luvussa käsitellään primitiivijuuria modulo alkuluvut.

In document Ollin Opas Olympiatason Ongelmanratkaisuun (sivua 102-110)