Kiinalainen jäännöslause

Kiinalainen jäännöslause on matematiikassa lukuteoriaan, tarkemmin sanottuna kongruensseihin liittyvä tulos.

Teoreema 
Teoreeman julkaisi ensimmäisen kerran kiinalainen matemaatikko Sun Tzu kolmannella vuosisadalla. Vuonna 1247 toinen kiinalainen matemaatikko Qin Jiushao käsitteli teoreemaa kirjassaan. Myös intialainen 600-luvun matemaatikko Brahmagupta tunsi lauseen versioita ja lause on esitetty myös Fibonaccin kirjassa Liber Abaci (1202). 

Olkoot n1, n2, …, nk positiivisia kokonaislukuja jotka ovat pareittain keskenään jaottomia. Silloin mille tahansa kokonaisluvuille a1,a2, …, ak, on olemassa kokonaisluku x joka ratkaisee kongruenssiyhtälöryhmän

Lisäksi kaikki ratkaisut x ovat kongruentteja modulo N, missä N = n1n2…nk.

Näin ollen , kaikille , jos ja vain jos .

Joissain tapauksissa kongruenssiyhtälöryhmät voidaan ratkaista vaikka ni:t eivät olisi pareittain keskenään jaottomia.
Ratkaisu x on olemassa jos ja vain jos:

Kaikki ratkaisut x ovat siten kongruentteja modulo pienin yhteinen jaettava (pyj) ni.

Teoreema voidaan esittää myös modernimmassa algebrallisessa muodossa seuraavasti:

Kokonaislukujen modulo  rengas  ,jossa  voidaan kirjoittaa alkulukujen tulona seuraavasti . 

Kun :t ovat eri alkulukuja, niin rengas  on luonnollisesti isomorfinen tulorenkaan  kanssa.

Todistus 

Tässä esitettävä todistus on muotoiltu Kenneth H. Rosen kirjan Elementary Number Theory and Its Applications (1993) perusteella.

Jaetaan todistus kahteen osaan. Konstruoidaan ensin ratkaisu ja todistetaan sitten ratkaisun yksikäsitteisyys.

Konstruoidaan ensin ratkaisu:

Merkitään . Koska luvut  ovat pareittain suhteellisia alkulukuja, niin . Näin ollen luvulla  on käänteisluku modulo . Merkitään tätä käänteislukua symbolilla , jolloin .

Nyt voimme muodostaa summan

.

Osoitetaan nyt, että kokonaisluku  on kongruenssiryhmän ratkaisu. Tehdään tämä osoittamalla, että  kaikilla .
Koska , kun , niin , kun . Näin ollen, . Koska , niin . Siis  on kongruenssiryhmän ratkaisu.
 
Todistetaan, että ratkaisu on yksikäsitteinen modulo . Olkoot  ja  kaksi kongruenssiryhmän ratkaisua. Silloin jokaista lukua  kohti on , joten jokaista lukua  kohti . Näin ollen  eli  .

Ratkaisukaava 
Kun :t ovat pareittain suhteellisia alkulukuja voidaan kongruenssiyhtälöryhmä ratkaista seuraavan kaavan avulla:

,

missä kertoimet  saadaan ratkaistua yhtälöstä

.

Laskuesimerkki 
Alkuperäinen Sun Tsun ongelma kuuluu seuraavasti. Kuinka monta sotilasta on Han Xingin armeijassa? Jos sotilaat marssivat kolmen riveissä, kaksi sotilasta jää yli. Jos he marssivat viiden riveissä, kolme jää yli, ja jos he marssivat seitsemän riveissä, kaksi jää yli?

Ongelma voidaan ilmaista kongruenssiyhtälöryhmänä:

Luvut 3, 5 ja 7 ovat pareittain jaottomia keskenään, joten voimme soveltaa kiinalaista jäännöslausetta. Nyt . Ratkaistaan ensin kertoimet :

Kokeilemalla ratkeaa , , . Sotilaiden määräksi saadaan:

Sotilaiden määrä voi siis olla 23, 128, 233, 338, ...

Lähteet

Aiheesta muualla 

 Kiinalainen jäännöslause ja sen sovelluksia
 Kiinalainen jäännöslause MathWorldissa (englanniksi)
 http://solmu.math.helsinki.fi/2012/3/kiinalainen.pdf

 Lukuteoria
Matemaattiset teoreemat