21  Kiinalainen jäännös­lause

Tekijä

Olli Järviniemi

21.1 Johdanto

Kiinalainen jäännös­lause liittyy seuraavanlaiseen ideaan: ”luvun parillisuus ei kerro mitään sen jako­jäännöksestä kolmella jaettaessa”. Tässä tekstissä esitetään lause, annetaan todistus ja demonstroidaan lauseen hyödyllisyyttä esimerkkien kautta.

21.2 Kiinalainen jäännös­lause

Tehtävä 21.1 Oletetaan, että kokonais­luku xx toteuttaa yhtälön x≡1(mod⁡3)x \equiv 1 \pmod{3}. Mitä arvoja xx voi saada modulo 55?

Tutkitaan pieniä xx:n arvoja, joilla x≡1(mod⁡3)x \equiv 1 \pmod{3}.

  • x=1x = 1: Tällöin x≡1(mod⁡5)x \equiv 1 \pmod{5}
  • x=4x = 4: Tällöin x≡4(mod⁡5)x \equiv 4 \pmod{5}
  • x=7x = 7: Tällöin x≡2(mod⁡5)x \equiv 2 \pmod{5}
  • x=10x = 10: Tällöin x≡0(mod⁡5)x \equiv 0 \pmod{5}
  • x=13x = 13: Tällöin x≡3(mod⁡5)x \equiv 3 \pmod{5}
  • x=16x = 16: Tällöin x≡1(mod⁡5)x \equiv 1 \pmod{5}
  • x=19x = 19: Tällöin x≡4(mod⁡5)x \equiv 4 \pmod{5}

Teemme kaksi huomiota:

  • Luku xx saa kaikki mahdolliset arvot modulo 55. Siis tieto siitä, mitä xx on modulo 33 ei kerro mitään siitä, mitä xx on modulo 55.
  • Samat arvot toistuvat 1515:n välein: x=1x = 1 ja x=16x = 16 antavat samat jako­jäännökset kolmella ja viidellä jaettaessa, kuten myös x=4x = 4 ja x=19x = 19.

Kiinalainen jäännös­lause kertoo juuri tästä ilmiöstä.

Lause 21.1 (Kiinalainen jäännös­lause) Olkoot m1,…,mkm_1, \ldots , m_k positiivisia kokonais­lukuja. Oletetaan, että luvut mim_i ovat pareittain yhteis­tekijättömiä, eli että syt(mi,mj)=1\text{syt}(m_i, m_j) = 1 kaikilla i≠ji \neq j. Olkoot a1,…,aka_1, \ldots , a_k mielivaltaisia kokonais­lukuja. Tällöin on olemassa sellainen kokonais­luku xx, että {x≡a1(mod⁡m1)x≡a2(mod⁡m2)⋮x≡ak(mod⁡mk). \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k}. \end{cases} Lisäksi tämä xx on yksi­käsitteinen modulo m1m2⋯mkm_1m_2 \cdots m_k.

Toisin sanoen tiedot siitä, mitä xx on modulo m1,m2,…m_1, m_2, \ldots ja mkm_k, voidaan yhdistää tiedoksi siitä, mitä xx on modulo m1⋯mkm_1 \cdots m_k.

Lauseessa tehdään oletus siitä, ettei luvuilla mim_i ole yhteisiä tekijöitä. Tämä oletus on tietysti tarpeen: esimerkiksi luvun arvo modulo 44 kertoo jotakin luvun arvosta modulo 66, koska arvo modulo 44 kertoo luvun parillisuuden, mikä puolestaan näkyy arvossa modulo 66.

21.3 Kiinalaisen jäännös­lauseen todistus

Kiinalaista jäännös­lausetta voi visualisoida luku­pyörien kautta, joista ensimmäisessä on m1m_1 lukua, toisessa m2m_2 ja niin edelleen. Alla on esitetty luku­pyörät tapauksessa m1=3,m2=5,m3=7m_1 = 3, m_2 = 5, m_3 = 7.

Kolmeen lohkoon jaettu lukupyörä eli rengas, jonka lohkoissa ovat luvut 0, 1 ja 2. Luku 0 on alhaalla lukuasennossa.

Viiteen lohkoon jaettu lukupyörä, jonka lohkoissa ovat luvut 0, 1, 2, 3 ja 4. Luku 0 on alhaalla lukuasennossa.

Seitsemään lohkoon jaettu lukupyörä, jonka lohkoissa ovat luvut 0-6. Luku 0 on alhaalla lukuasennossa.

Kuva 21.1: Luku­pyörät tapauksessa m1=3,m2=5,m3=7m_1 = 3, m_2 = 5, m_3 = 7.

Kullekin kokonais­luvulle xx pyörät voidaan asettaa sellaiseen asentoon, joka kertoo luvun xx jako­jäännökset luvuilla m1,…,mkm_1, \ldots , m_k jaettaessa. Kuva 1 näyttää asennon, joka vastaa lukua x=0x = 0.

Kun lukua xx kasvattaa yhdellä, kutakin pyörää pyöritetään yksi askel eteenpäin. Lukua xx kasvatettaessa pyörien asennot muodostavat erilaisia yhdistelmiä. Esimerkiksi 3737 askeleen jälkeen pyörät asettuvat seuraavaan asemaan, kertoen luvun x=37x = 37 jako­jäännökset luvuilla mim_i jaettaessa.

Kolmen lohkon lukupyörä pyöräytettynä niin, että luku 1 on alhaalla lukuasennossa. Tämä vastaa jakojäännöstä 1, kun 37 jaetaan kolmella.

Viiden lohkon lukupyörä pyöräytettynä niin, että luku 2 on alhaalla lukuasennossa. Tämä vastaa jakojäännöstä 2, kun 37 jaetaan viidellä.

Seitsemän lohkon lukupyörä pyöräytettynä niin, että luku 2 on alhaalla lukuasennossa. Tämä vastaa jakojäännöstä 2, kun 37 jaetaan seitsemällä.

Kuva 21.2: Luku­pyörät, kun kutakin on pyöräytetty 3737 kertaa eteenpäin kuvan 21.1 tilanteesta.

Pyörien asennot kertovat, että 37≡1(mod⁡3)37 \equiv 1 \pmod{3}, 37≡2(mod⁡5)37 \equiv 2 \pmod{5} ja 37≡2(mod⁡7)37 \equiv 2 \pmod{7}.

Kiinalainen jäännös­lause väittää, että kaikki pyörien asentojen yhdistelmät ovat mahdollisia ja että samat yhdistelmät toistuvat tasan m1⋯mkm_1 \cdots m_k askeleen välein.

Todistetaan lause. Teemme tämän kahdessa osassa. Ensin mietimme, kuinka usein sama asento voi esiintyä, minkä jälkeen osoitamme, että jokainen asento todella esiintyy.

Asentojen toistuminen. Kuinka usein sama pyörien asentojen yhdistelmä voi esiintyä? Mietitään vaikkapa kuvan 2 tilannetta. Kuinka monta askelta pitää mennä eteenpäin, jotta päädymme taas tilanteeseen, jossa ensimmäisessä pyörässä on luku 11, toisessa 22 ja kolmannessa 22? Vastaus: 3⋅5⋅7=1053 \cdot 5 \cdot 7 = 105 askelta. Alla perustelu (yleisessä tapauksessa).

Kuvitellaan, että lähdemme lukua xx vastaavasta yhdistelmästä ja suorittamalla TT askelta päädymme samaan tilanteeseen. Tämä tarkoittaa, että x+T≡x(mod⁡m1)x+T≡x(mod⁡m2)⋮x+T≡x(mod⁡mk). \begin{aligned} x + T & \equiv x \pmod{m_1} \\ x + T & \equiv x \pmod{m_2} \\ & \vdots \\ x + T & \equiv x \pmod{m_k}. \end{aligned} Tästä seuraa, että T≡0(mod⁡m1),T≡0(mod⁡m2),…,T≡0(mod⁡mk)T \equiv 0 \pmod{m_1}, T \equiv 0 \pmod{m_2}, \ldots , T \equiv 0 \pmod{m_k}. Siis TT on jaollinen kullakin luvuista m1,m2,…,mkm_1, m_2, \ldots , m_k. Koska oletimme lukujen mim_i olevan pareittain yhteis­tekijättömiä, saadaan tästä m1m2⋯mk∣T.m_1m_2 \cdots m_k \mid T.

Toisaalta on selvää, että sama asentojen yhdistelmä toistuu m1⋯mkm_1 \cdots m_k askeleen välein. Siis sama tilanne toistuu vain ja ainoastaan m1⋯mkm_1 \cdots m_k askeleen välein.

Kaikkien asentojen esiintyminen. Mietitään lukuja x=0,1,…,m1m2⋯mk−1x = 0, 1, \ldots , m_1m_2 \cdots m_k - 1. Kutakin näistä luvuista vastaa jokin pyörien asentojen yhdistelmä.

Todistuksen ensimmäisen osan nojalla millään kahdella näistä luvuista ei ole samaa yhdistelmää. Koska tutkittavia lukuja on m1m2⋯mkm_1m_2 \cdots m_k kappaletta ja pyörien mahdollisia asentoja on m1m2⋯mkm_1m_2 \cdots m_k kappaletta, vastaa jokaista asentoa täsmälleen yksi luku. Siis jokainen yhdistelmä todella esiintyy, ja todistus on valmis.

21.4 Sovelluksia

Alla esitetään kolme erilaista sovellus­kohdetta kiinalaiselle jäännös­lauseelle. Ensimmäisen teema on konstruktio: haluamme löytää tietynlaisen kokonais­luvun, ja kiinalainen jäännös­lause todistaa sellaisen olemassa­olon. Toisen teema on yhdistäminen: eri moduloilla saatavia tietoja voi yhdistellä. Kolmannen teema on hajottaminen: isompi ongelma voidaan kiinalaisen jäännös­lauseen avulla hajottaa pienempiin ongelmiin, jotka osataan ratkaista.

Tehtävä 21.2 Osoita, että on olemassa jotkin 100100 peräkkäistä positiivista kokonais­lukua, joista kullakin on vähintään 100100 tekijää.

Haluamme siis löytää positiivisen kokonais­luvun xx, jolla kullakin luvuista x,x+1,…,x+99x, x+1, \ldots , x+99 on vähintään 100100 tekijää. Meillä on melko paljon valinnan­varaa: muuta ei vaadita kuin että kullakin luvuista x+ix+i on paljon tekijöitä, mutta saamme itse päättää, mitä nämä tekijät ovat.

Valitaan jotkin positiiviset kokonais­luvut m1,…,m100m_1, \ldots , m_{100} ja yritetään valita xx niin, että xx on jaollinen luvulla m1m_1, x+1x+1 luvulla m2m_2 ja niin edelleen. Tämä voidaan muotoilla kongruenssien kautta muodossa {x≡0(mod⁡m1)x+1≡0(mod⁡m2)⋮x+99≡0(mod⁡m100). \begin{cases} x & \equiv 0 \pmod{m_1} \\ x + 1 & \equiv 0 \pmod{m_2} \\ \vdots \\ x + 99 & \equiv 0 \pmod{m_{100}}. \end{cases} Mitä ehtoja haluamme lukujen mim_i toteuttavan? Ensinnäkin haluamme, että kullakin niistä on vähintään 100100 tekijää, jotta tehtävä ratkeaa. Toiseksi luvut mim_i kannata valita olemaan pareittain yhteis­tekijättömiä, jotta pääsemme käyttämään kiinalaista jäännös­lausetta. Molemmat näistä valinnoista voidaan toteuttaa. Voidaan valita vaikka m1m_1 olemaan ensimmäisen sadan alku­luvun tulo, m2m_2 olemaan seuraavan sadan alku­luvun tulo ja niin edelleen. Nyt yllä olevalla yhtälö­ryhmällä on kiinalaisen jäännös­lauseen nojalla ratkaisu: yhtälö­ryhmähän voidaan kirjoittaa muodossa {x≡0(mod⁡m1)x≡−1(mod⁡m2)⋮x≡−99(mod⁡m100) \begin{cases} x \equiv 0 \pmod{m_1} \\ x \equiv -1 \pmod{m_2} \\ \vdots \\ x \equiv -99 \pmod{m_{100}} \end{cases} Tämä ratkaisu xx toteuttaa tehtävän­annon ehdon (kunhan vain valitaan xx olemaan positiivinen, mikä voidaan tehdä).

Tehtävä 21.3 Polynomin PP kertoimet ovat kokonais­lukuja. Tiedetään, että on olemassa kokonais­luku aa, jolla P(a)P(a) on jaollinen kymmenellä. Tiedetään myös, että on olemassa kokonais­luku bb, jolla P(b)P(b) on jaollinen seitsemällä. Osoita, että on olemassa kokonais­luku cc, jolla P(c)P(c) on jaollinen luvulla 7070.

Haluamme yhdistää lukujen aa ja bb ne ominaisuudet, joiden ansiosta P(a)P(a) ja P(b)P(b) ovat jaollisia kymmenellä ja seitsemällä. Tämä onnistuu kohtalaisen helposti: kiinalaisen jäännös­lauseen nojalla on olemassa kokonais­luku cc, jolla {c≡a(mod⁡10)c≡b(mod⁡7). \begin{cases} c \equiv a \pmod{10} \\ c \equiv b \pmod{7}. \end{cases} Ensimmäisen yhtälön ja kongruenssien perus­ominaisuuksien nojalla nyt pätee P(c)≡P(a)(mod⁡10)P(c) \equiv P(a) \pmod{10}. Oletuksen nojalla P(a)≡0(mod⁡10)P(a) \equiv 0 \pmod{10}, joten P(c)P(c) on jaollinen kymmenellä. Vastaavasti P(c)≡P(b)≡0(mod⁡7)P(c) \equiv P(b) \equiv 0 \pmod{7}, joten P(c)P(c) on jaollinen seitsemällä. Täten P(c)P(c) on jaollinen myös luvulla 10⋅7=7010 \cdot 7 = 70.

Tehtävä 21.4 Onko olemassa kokonais­lukua xx, jolla x2+1x^2 + 1 on jaollinen luvulla 650650?

Voisimme periaatteessa käydä kaikki luvut modulo 650650 läpi ja katsoa, saadaanko ratkaisua. On kuitenkin paljon tehokkaampi tapa.

Huomataan, että luvun 650650 alku­tekijä­hajotelma on 650=2⋅52⋅13.650 = 2 \cdot 5^2 \cdot 13. On luontevaa tutkia, voiko x2+1x^2 + 1 olla jaollinen luvuilla 2,522, 5^2 ja 1313 erikseen. Jos on, niin nämä jaollisuus­ehdot voidaan yhdistää samaan tapaan kuin edellisessä tehtävässä. Olemme siis saaneet hajotettua tehtävän pienempiin tapauksiin.

Käsitellään nämä pienemmät tapaukset. Yhtälöllä x2+1≡0(mod⁡2)x^2 + 1 \equiv 0 \pmod{2} on ratkaisu x≡1(mod⁡2).x \equiv 1 \pmod{2}. Yhtälön x2+1≡0(mod⁡52)x^2 + 1 \equiv 0 \pmod{5^2} tapauksessa voitaisiin käydä kaikki 2525 vaihto­ehtoa läpi. Hakua saa hieman nopeutettua huomaamalla, että yhtälöllä x2+1≡0(mod⁡5)x^2 + 1 \equiv 0 \pmod{5} on ratkaisut x≡2(mod⁡5)x \equiv 2 \pmod{5} ja x≡3(mod⁡5)x \equiv 3 \pmod{5}, joten myös modulo 525^2 ratkaisun tulee olla 22 tai 33 modulo 55. Jäljelle jää vain 1010 vaihto­ehtoa, ja löydetään ratkaisu x≡7(mod⁡25).x \equiv 7 \pmod{25}. (Myös x≡18(mod⁡25)x \equiv 18 \pmod{25} kävisi.) Modulo 1313 löydetään x≡5(mod⁡13).x \equiv 5 \pmod{13}. (Myös x≡8(mod⁡13)x \equiv 8 \pmod{13} kävisi.)

Eli jokaiselle yksittäiselle alku­luvun potenssille löytyi ratkaisu. Kiinalaisen jäännös­lauseen nojalla yhtälö­ryhmällä {x≡1(mod⁡2)x≡7(mod⁡25)x≡5(mod⁡13) \begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 7 \pmod{25} \\ x \equiv 5 \pmod{13} \end{cases} on ratkaisu. Tällä ratkaisulla pätee x2+1≡0(mod⁡650)x^2 + 1 \equiv 0 \pmod{650}, eli vastaus tehtävään on kyllä.

21.5 Tehtäviä

Tehtävä 1. Ratkaise yhtälö­pari x≡3(mod⁡5)x \equiv 3 \pmod{5}, x≡2(mod⁡7)x \equiv 2 \pmod{7}.

Tehtävä 2. Ratkaise yhtälö­ryhmä {x≡1(mod⁡2)x≡2(mod⁡3)x≡3(mod⁡5)x≡4(mod⁡7). \begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 4 \pmod{7}. \end{cases}

Tehtävä 3. Osoita, että on olemassa miljoona peräkkäistä positiivista kokonais­lukua, joista mikään ei ole alku­luku.

Tehtävä 4. Olkoot xx ja yy kokonais­lukuja. Sanotaan, että koordinaatiston piste (x,y)(x, y) näkyy origosta, jos pisteiden (0,0)(0, 0) ja (x,y)(x, y) välisellä janalla ei ole muita pisteitä, joiden molemmat koordinaatit ovat kokonais­lukuja. Osoita, että on olemassa 100×100100 \times 100 -neliö, jonka mikään kokonais­luku­piste ei näy origosta.

Tehtävä 5. Olkoot nn ja mm positiivisia kokonais­lukuja, ja olkoon d=syt(n,m)d = \text{syt}(n, m). Osoita, että yhtälö­parilla {x≡a(mod⁡n)x≡b(mod⁡m) \begin{cases} x \equiv a \pmod{n} \\ x \equiv b \pmod{m} \end{cases} on kokonais­luku­ratkaisuja xx jos ja vain jos a≡b(mod⁡d)a \equiv b \pmod{d}, ja osoita, että ratkaisut ovat yksi­käsitteisiä modulo pyj(n,m)\text{pyj}(n, m).