Eulerin lause

Fermat’n pieni lause on hyvä tulos, mutta onko olemassa vastaavaa väitettä muille kuin alkulukumoduloille? On, mutta muotoilu on aavistuksen verran teknisempi.

Ensin määritellään𝜑-funktio.³⁵

35𝜑lausutaan ”fii”.

Määritelmä

Olkoon 𝑛 positiivinen kokonaisluku. Määritellään 𝜑(𝑛) olemaan niiden koko-naislukujen 𝑚 määrä, joilla 1≤𝑚≤𝑛 ja syt(𝑚, 𝑛) = 1.

Esimerkki

Pätee 𝜑(6) = 2, koska mahdollisista kandidaateista 1,2,3,4,5 ja 6ainoastaan kaksi ovat yhteistekijättömiä luvun 6kanssa, nimittäin luvut 1ja 5.

Esimerkki

Kaikilla alkuluvuilla𝑝pätee𝜑(𝑝) =𝑝−1, koska kandidaateista1,2, . . . , 𝑝−1, 𝑝 ainoastaan luku𝑝 ei kelpaa.

Esimerkki

Olkoon 𝑝 alkuluku ja 𝑘 ≥1 kokonaisluku. Tällöin 𝜑(𝑝^𝑘) = 𝑝^𝑘−𝑝^𝑘−1, koska kandidaateista1,2, . . . , 𝑝^𝑘 kelpaavat kaikki paitsi ne, jotka ovat jaollisia luvulla 𝑝. Epäkelpaavia lukuja on 𝑝^𝑘−1, joten kelpaavia on𝑝^𝑘−𝑝^𝑘−1.

Seuraava tulos yleistää Fermat’n pientä lausetta.

Lause (Eulerin lause)

Olkoon 𝑛 positiivinen kokonaisluku, ja olkoon 𝑎 sellainen kokonaisluku, että syt(𝑎, 𝑛) = 1. Tällöin

𝑎^𝜑(𝑛)≡1 (mod 𝑛).

Eulerin lauseen todistus on käytännössä katsoen sama kuin edellä esitetty Fermat’n pienen lauseen todistus. Tällä kertaa joukoksi 𝑆 valitaan niiden lukujen 𝑠 joukko, joilla 1 ≤ 𝑠 ≤ 𝑛 ja syt(𝑠, 𝑛) = 1, ja joukoksi 𝑇 luvut muotoa 𝑎𝑠, missä 𝑠 ∈ 𝑆. Yksityiskohtainen tarkastelu jätetään lukijalle.

Käytännön tarkoituksia varten 𝜑-funktion arvoja olisi kiva osata laskea. Seuraava tulos antaa suoran kaavan funktion arvoille.

Lemma

Olkoon 𝑛 positiivinen kokonaisluku, jonka alkutekijähajotelma on 𝑛 =𝑝^𝑎₁¹𝑝^𝑎₂²· · ·𝑝^𝑎_𝑘^𝑘.

Tällöin

𝜑(𝑛) = ∏︁

1≤𝑖≤𝑘

𝑝^𝑎_𝑖^𝑖−1(𝑝𝑖−1).

Kaavan voi myös kirjoittaa sievemmin muotoon

𝜑(𝑛) =𝑛 ∏︁

1≤𝑖≤𝑘

(︂

1− 1 𝑝𝑖

)︂

.

Väitteen todistus perustuu siihen faktaan, että 𝜑(𝑝^𝑎) =𝑝^𝑎−1(𝑝−1) kaikilla alkulu-vuilla𝑝ja kokonaisluvuilla 𝑎≥1. Tämä todistettiin jo edellä esitetyissä esimerkeissä.

Enää tulee yhdistää nämä tiedot.³⁶

Ideana on käyttää kiinalaista jäännöslausetta. Tutkitaan kandidaatteja 1,2, . . . , 𝑛. Valitaan jokin kandidaatti𝑥. Tämä𝑥määräytyy yksikäsitteisesti, kun tiedetään, mitä 𝑥on modulo𝑝^𝑎_𝑖^𝑖 kaikilla 𝑖: tällöin kiinalaisen jäännöslauseen avulla tiedetään, mitä𝑥 on modulo𝑛. Lisäksi kandidaatti𝑥 on kelpaava jos ja vain jos 𝑥on yhteistekijätön kaikkien lukujen 𝑝^𝑎_𝑖^𝑖 kanssa.

Voimme siis luoda kaikki kelpaavat luvut 𝑥 seuraavalla tavalla: Valitaan koko-naisluvut𝑏₁, 𝑏₂, . . . , 𝑏_𝑘, joilla𝑏_𝑖 ja𝑝^𝑎_𝑖^𝑖 ovat yhteistekijättömiä kaikilla 𝑖, ja valitaan𝑥 olemaan (kiinalaisen jäännöslauseen) yhtälöryhmän𝑥≡𝑏_𝑖 (mod 𝑝^𝑎_𝑖^𝑖)ratkaisu väliltä [1, 𝑛]. Käymällä läpi kaikki vaihtoehdot luvuille 𝑏₁, 𝑏₂, . . . , 𝑏_𝑘 saadaan kelpaavat luvut täsmälleen kerran, kun vaaditaan vielä, että0≤𝑏_𝑖 < 𝑝^𝑎_𝑖^𝑖 kaikilla 𝑖.

Kuinka monta vaihtoehtoa luvuille 𝑏₁, 𝑏₂, . . . , 𝑏_𝑛 on? Yksittäiselle 𝑏_𝑖 on 𝜑(𝑝^𝑎_𝑖^𝑖) vaihtoehtoa, ja kertomalla yksittäisten lukujen 𝑏_𝑖 vaihtoehtojen määrä saadaan kelpaavien lukujen määrä. Tämä todistaa halutun väitteen.

Seuraavana esitetään ratkaisu Johdantotehtäviä-luvussa esitettyyn tehtävään. Rat-kaisussa kantavana teemana on eksponenttifunktioiden jaksollisuus kongruensseissa.

Tehtävä

Etsi kaikki positiiviset kokonaisluvut 𝑥 ja 𝑦, joilla |3^𝑥−2^𝑦|= 1.

Käytännössä ratkaistavana on kaksi eri yhtälöä. Ensimmäinen on 3^𝑥 −2^𝑦 = 1 ja toinen 3^𝑥−2^𝑦 = −1. Ensimmäisellä näistä on ainakin kaksi ratkaisua (𝑥, 𝑦) = (1,1),(2,3), ja toisella on ainakin yksi ratkaisu (𝑥, 𝑦) = (1,2). Voisi veikata, että se yhtälö, jolla on enemmän ratkaisuja, on vaikeampi. Aloitetaan siis yhtälöstä 3^𝑥−2^𝑦 =−1.

Yksi idea yhtälön ratkaisemiseksi on tutkia sitä modulo 𝑚 jollain positiivisella kokonaisluvulla 𝑚. Jos nimittäin pätee 3^𝑥 −2^𝑦 = −1, niin pätee 3^𝑥 − 2^𝑦 ≡ −1 (mod 𝑚) kaikilla𝑚. Tätä kautta voisimme saada tietoa luvuista𝑥 ja 𝑦.

Millainen olisi hyvä 𝑚? Ainakin jos 𝑚 on kakkosen tai kolmosen potenssi, niin jompikumpi termeistä 3^𝑥 ja 2^𝑦 on 0 modulo 𝑚 (kun muuttujien 𝑥 ja 𝑦 arvot ovat suuria). Valitaan ensiksi 𝑚= 3. Nyt pätee−2^𝑦 ≡ −1 (mod 3), eli2^𝑦 ≡1 (mod 3). Tämä selvästikin vaatii, että 𝑦 on parillinen. Saimme siis tietoa luvusta 𝑦, mikä on tietysti edistystä, mutta tehtävä ei ole vielä ratkennut. Kokeillaan muita luvun 𝑚 valintoja.

Valitaan 𝑚 = 4. Koska 𝑦 on parillinen, niin 𝑦≥2, ja tällöin −1≡3^𝑥−2^𝑦 ≡ 3^𝑥 (mod 4). Tästä saadaan ehto 𝑥 ≡ 1 (mod 2). Yritetään vielä seuraavaa sellaista

36Jälleen lokaalit tiedot yhdistetään globaaliksi tulokseksi.

luvun 𝑚 arvoa, joka on kakkosen tai kolmosen potenssi, eli lukua 𝑚= 8. Jos 𝑦≥3, niin −1≡3^𝑥−2^𝑦 ≡3^𝑥 (mod 8). Tällä yhtälöllä ei kuitenkaan ole ratkaisuja, koska luvun 3potenssit ovat aina 1 tai3 modulo 8. Siis ainoa mahdollisuus on 𝑦= 2, ja tästä saadaan ratkaisu 𝑥= 1 ja 𝑦= 2.

Tutkitaan sitten yhtälöä 3^𝑥−2^𝑦 = 1. Kuten edellä voimme tutkia yhtälöä modulo kakkosen ja kolmosen potenssit. Esimerkiksi modulo16saadaan (olettaen, että𝑦≥4) ehto𝑥≡0 (mod 4). Modulo 9 saadaan (olettaen, että𝑥≥2) ehto 𝑦≡3 (mod 6)

Yhtälöä voisi tutkia vielä esimerkiksi modulo64 ja modulo 81. Huomataan kuiten-kin, että vaikka yhtälöistä saadaan lisää tietoa luvuista𝑥ja𝑦, niin emme kuitenkaan saa rajoitettua yhtälön ratkaisuja. Täytyy siis keksiä jotain muuta.

Voisimmeko jotenkin hyödyntää saatuja tietoja 𝑥≡0 (mod 4) ja𝑦≡3 (mod 6)? Ainakin tietoa 𝑥≡ 0 (mod 4) voisi hyödyntää valitsemalla moduloksi 𝑚 sellaisen luvun, että kolmosen potenssien jakso modulo𝑚 on jaollinen neljällä. Helpoin tapa toteuttaa tämä idea on valita𝑚 = 5, jolloin Fermat’n pienen lauseen nojalla kolmosen potenssit toistuvat modulo5neljän jaksoissa. (Tämän voi tietysti myös tarkistaa tässä tapauksessa käsin). Koska tiedämme, että 𝑥≡ 0 (mod 4), niin pätee 3^𝑥 ≡ 3⁰ ≡ 1 (mod 5). Täten

1 = 3^𝑥−2^𝑦 ≡1−2^𝑦 (mod 5), joten2^𝑦 on jaollinen viidellä. Tämä on selvästi mahdotonta.

Muistetaan, että aiemmin teimme oletukset𝑦≥4ja𝑥≥2. Käytimme lopulta vain oletuksella𝑦≥4saatavaa tietoa, joten tulee enää käsitellä ne tapaukset, joissa𝑦 <4. Näiden tapausten läpikäynti on helppoa, ja saamme ratkaisut (𝑥, 𝑦) = (1,1),(2,3).

Kaiken kaikkiaan johdantokappaleessa löydetyt ratkaisut(𝑥, 𝑦) = (1,1),(1,2),(2,3) ovat yhtälön|3^𝑥−2^𝑦|= 1 ainoat ratkaisut.

Kommentti: Jos tutkisimme polynomiyhtälöitä eli vaikkapa yhtälöä 𝑥²−3𝑦² = 17 (joka esiintyy myöhemmin esimerkkitehtävänä), niin emme voisi mitenkään yhdistellä eri (yhteistekijättömillä) moduloilla saatavia tietoja. Tämä johtuu siitä, että vaikkapa modulo 2 yhtälöstä saadaan ehtoja siitä, mitä𝑥 ja 𝑦 ovat modulo 2, ja tutkiminen modulo 5antaa tietoa siitä, mitä 𝑥 ja 𝑦 ovat modulo 5. Kiinalaisen jäännöslauseen perusteella nämä ehdot eivät kommunikoi mitenkään keskenään.

Tässä tehtävässä tilanne on kuitenkin toinen. Tutkimalla modulo16saimme tiedon 𝑥≡0 (mod 4). Tämä kertoo, mitä 3^𝑥 on modulo 5. Syy tähän eroon polynomien ja eksponenttifunktioiden välillä on arvojen jaksollisuus: polynomien arvot ovat jaksollisia modulo 𝑚 jaksolla 𝑚, mutta eksponenttifunktioiden jaksot ovat jotain aivan muuta. Esimerkiksi kolmosen potenssit ovat jaksollisia jaksolla neljä sekä modulo16 että modulo5. Yhteistekijättömät modulot 16 ja 5 siis kommunikoivat keskenään, toisin kuin polynomien tapauksessa.

Näillä ideoilla saamme myös käsitystä siitä, miten tehtävässä kannattaa valita eri moduloita 𝑚: Valitaan niitä niin, että saamme mahdollisimman paljon toisistaan riippuvia kongruenssiehtoja luvuille𝑥 ja 𝑦. Tämä saavutetaan valitsemalla modu-loksi 𝑚 sellaisia lukuja, että lukujen 2 ja 3 potenssien jaksojen pituudet modulo 𝑚 sisältävät paljon yhteisiä tekijöitä. Ratkaisussa tämä saavutettiin kolmosen

po-tensseille arvoilla 𝑚 = 16 ja 𝑚 = 5, joilla nämä jaksojen pituudet olivat samat.³⁷ Eksponenttifunktioiden jaksollisuuden tutkimista jatketaan seuraavassa luvussa.