Kiinalainen jäännöslause liittyy seuraavanlaiseen ideaan: ”luvun parillisuus ei kerro mitään sen jakojäännöksestä kolmella jaettaessa”. Tässä tekstissä esitetään lause, annetaan todistus ja demonstroidaan lauseen hyödyllisyyttä esimerkkien kautta.
21.2 Kiinalainen jäännöslause
Tehtävä 21.1 Oletetaan, että kokonaisluku toteuttaa yhtälön . Mitä arvoja voi saada modulo ?
Tutkitaan pieniä :n arvoja, joilla .
: Tällöin
: Tällöin
: Tällöin
: Tällöin
: Tällöin
: Tällöin
: Tällöin
Teemme kaksi huomiota:
Luku saa kaikki mahdolliset arvot modulo . Siis tieto siitä, mitä on modulo ei kerro mitään siitä, mitä on modulo .
Samat arvot toistuvat :n välein: ja antavat samat jakojäännökset kolmella ja viidellä jaettaessa, kuten myös ja .
Kiinalainen jäännöslause kertoo juuri tästä ilmiöstä.
Lause 21.1 (Kiinalainen jäännöslause) Olkoot positiivisia kokonaislukuja. Oletetaan, että luvut ovat pareittain yhteistekijättömiä, eli että kaikilla . Olkoot mielivaltaisia kokonaislukuja. Tällöin on olemassa sellainen kokonaisluku , että Lisäksi tämä on yksikäsitteinen modulo .
Toisin sanoen tiedot siitä, mitä on modulo ja , voidaan yhdistää tiedoksi siitä, mitä on modulo .
Lauseessa tehdään oletus siitä, ettei luvuilla ole yhteisiä tekijöitä. Tämä oletus on tietysti tarpeen: esimerkiksi luvun arvo modulo kertoo jotakin luvun arvosta modulo , koska arvo modulo kertoo luvun parillisuuden, mikä puolestaan näkyy arvossa modulo .
21.3 Kiinalaisen jäännöslauseen todistus
Kiinalaista jäännöslausetta voi visualisoida lukupyörien kautta, joista ensimmäisessä on lukua, toisessa ja niin edelleen. Alla on esitetty lukupyörät tapauksessa .
Kuva 21.1: Lukupyörät tapauksessa .
Kullekin kokonaisluvulle pyörät voidaan asettaa sellaiseen asentoon, joka kertoo luvun jakojäännökset luvuilla jaettaessa. Kuva 1 näyttää asennon, joka vastaa lukua .
Kun lukua kasvattaa yhdellä, kutakin pyörää pyöritetään yksi askel eteenpäin. Lukua kasvatettaessa pyörien asennot muodostavat erilaisia yhdistelmiä. Esimerkiksi askeleen jälkeen pyörät asettuvat seuraavaan asemaan, kertoen luvun jakojäännökset luvuilla jaettaessa.
Kuva 21.2: Lukupyörät, kun kutakin on pyöräytetty kertaa eteenpäin kuvan 21.1 tilanteesta.
Pyörien asennot kertovat, että , ja .
Kiinalainen jäännöslause väittää, että kaikki pyörien asentojen yhdistelmät ovat mahdollisia ja että samat yhdistelmät toistuvat tasan 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 , toisessa ja kolmannessa ? Vastaus: askelta. Alla perustelu (yleisessä tapauksessa).
Kuvitellaan, että lähdemme lukua vastaavasta yhdistelmästä ja suorittamalla askelta päädymme samaan tilanteeseen. Tämä tarkoittaa, että Tästä seuraa, että . Siis on jaollinen kullakin luvuista . Koska oletimme lukujen olevan pareittain yhteistekijättömiä, saadaan tästä
Toisaalta on selvää, että sama asentojen yhdistelmä toistuu askeleen välein. Siis sama tilanne toistuu vain ja ainoastaan askeleen välein.
Kaikkien asentojen esiintyminen. Mietitään lukuja . 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 kappaletta ja pyörien mahdollisia asentoja on 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 sovelluskohdetta kiinalaiselle jäännöslauseelle. Ensimmäisen teema on konstruktio: haluamme löytää tietynlaisen kokonaisluvun, ja kiinalainen jäännöslause todistaa sellaisen olemassaolon. Toisen teema on yhdistäminen: eri moduloilla saatavia tietoja voi yhdistellä. Kolmannen teema on hajottaminen: isompi ongelma voidaan kiinalaisen jäännöslauseen avulla hajottaa pienempiin ongelmiin, jotka osataan ratkaista.
Tehtävä 21.2 Osoita, että on olemassa jotkin peräkkäistä positiivista kokonaislukua, joista kullakin on vähintään tekijää.
Haluamme siis löytää positiivisen kokonaisluvun , jolla kullakin luvuista on vähintään tekijää. Meillä on melko paljon valinnanvaraa: muuta ei vaadita kuin että kullakin luvuista on paljon tekijöitä, mutta saamme itse päättää, mitä nämä tekijät ovat.
Valitaan jotkin positiiviset kokonaisluvut ja yritetään valita niin, että on jaollinen luvulla , luvulla ja niin edelleen. Tämä voidaan muotoilla kongruenssien kautta muodossa Mitä ehtoja haluamme lukujen toteuttavan? Ensinnäkin haluamme, että kullakin niistä on vähintään tekijää, jotta tehtävä ratkeaa. Toiseksi luvut kannata valita olemaan pareittain yhteistekijättömiä, jotta pääsemme käyttämään kiinalaista jäännöslausetta. Molemmat näistä valinnoista voidaan toteuttaa. Voidaan valita vaikka olemaan ensimmäisen sadan alkuluvun tulo, olemaan seuraavan sadan alkuluvun tulo ja niin edelleen. Nyt yllä olevalla yhtälöryhmällä on kiinalaisen jäännöslauseen nojalla ratkaisu: yhtälöryhmähän voidaan kirjoittaa muodossa Tämä ratkaisu toteuttaa tehtävänannon ehdon (kunhan vain valitaan olemaan positiivinen, mikä voidaan tehdä).
Tehtävä 21.3 Polynomin kertoimet ovat kokonaislukuja. Tiedetään, että on olemassa kokonaisluku , jolla on jaollinen kymmenellä. Tiedetään myös, että on olemassa kokonaisluku , jolla on jaollinen seitsemällä. Osoita, että on olemassa kokonaisluku , jolla on jaollinen luvulla .
Haluamme yhdistää lukujen ja ne ominaisuudet, joiden ansiosta ja ovat jaollisia kymmenellä ja seitsemällä. Tämä onnistuu kohtalaisen helposti: kiinalaisen jäännöslauseen nojalla on olemassa kokonaisluku , jolla Ensimmäisen yhtälön ja kongruenssien perusominaisuuksien nojalla nyt pätee . Oletuksen nojalla , joten on jaollinen kymmenellä. Vastaavasti , joten on jaollinen seitsemällä. Täten on jaollinen myös luvulla .
Tehtävä 21.4 Onko olemassa kokonaislukua , jolla on jaollinen luvulla ?
Voisimme periaatteessa käydä kaikki luvut modulo läpi ja katsoa, saadaanko ratkaisua. On kuitenkin paljon tehokkaampi tapa.
Huomataan, että luvun alkutekijähajotelma on On luontevaa tutkia, voiko olla jaollinen luvuilla ja erikseen. Jos on, niin nämä jaollisuusehdot 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ä on ratkaisu Yhtälön tapauksessa voitaisiin käydä kaikki vaihtoehtoa läpi. Hakua saa hieman nopeutettua huomaamalla, että yhtälöllä on ratkaisut ja , joten myös modulo ratkaisun tulee olla tai modulo . Jäljelle jää vain vaihtoehtoa, ja löydetään ratkaisu (Myös kävisi.) Modulo löydetään (Myös kävisi.)
Eli jokaiselle yksittäiselle alkuluvun potenssille löytyi ratkaisu. Kiinalaisen jäännöslauseen nojalla yhtälöryhmällä on ratkaisu. Tällä ratkaisulla pätee , eli vastaus tehtävään on kyllä.
21.5 Tehtäviä
Tehtävä 1. Ratkaise yhtälöpari , .
Tehtävä 2. Ratkaise yhtälöryhmä
Tehtävä 3. Osoita, että on olemassa miljoona peräkkäistä positiivista kokonaislukua, joista mikään ei ole alkuluku.
Tehtävä 4. Olkoot ja kokonaislukuja. Sanotaan, että koordinaatiston piste näkyy origosta, jos pisteiden ja välisellä janalla ei ole muita pisteitä, joiden molemmat koordinaatit ovat kokonaislukuja. Osoita, että on olemassa -neliö, jonka mikään kokonaislukupiste ei näy origosta.
Tehtävä 5. Olkoot ja positiivisia kokonaislukuja, ja olkoon . Osoita, että yhtälöparilla on kokonaislukuratkaisuja jos ja vain jos , ja osoita, että ratkaisut ovat yksikäsitteisiä modulo .
