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 *n*1, *n*2, …, *n**k* positiivisia kokonaislukuja jotka ovat pareittain keskenään jaottomia. Silloin mille tahansa kokonaisluvuille *a*1,*a*2, …, *a**k*, on olemassa kokonaisluku *x* joka ratkaisee kongruenssiyhtälöryhmän

:\begin{align}
 x &\equiv a_1 \pmod{n_1} \\
 x &\equiv a_2 \pmod{n_2} \\
   &\vdots \\
 x &\equiv a_k \pmod{n_k}
\end{align}

Lisäksi kaikki ratkaisut *x* ovat kongruentteja modulo *N*, missä *N* = *n*1*n*2…*n**k*.

Näin ollen x \equiv y \pmod{n_i}, kaikille 1\leq i \leq k, jos ja vain jos x \equiv y \pmod{N}.

Joissain tapauksissa kongruenssiyhtälöryhmät voidaan ratkaista vaikka *n<sub>i</sub>*:t eivät olisi pareittain keskenään jaottomia.
Ratkaisu *x* on olemassa jos ja vain jos:

:a_i \equiv a_j \pmod.

Nyt voimme muodostaa summan

 x=a_{1}N_{1}b_{1}+a_{2}N_{2}b_{2}+...+a_{r}N_{r}b_{r}.

Osoitetaan nyt, että kokonaisluku  x  on kongruenssiryhmän ratkaisu. Tehdään tämä osoittamalla, että  x\equiv a_{k}\pmod{n_{k}} kaikilla k=1,2,...,r.
Koska n_{j}\mid N_{k}, kun j\neq k, niin N_{j}\equiv 0\pmod{n_{k}}. Näin ollen, x\equiv a_{k}N_{k}b_{k}\equiv a_{k}\pmod{n_{k}} . Koska N_{k}b_{k}\equiv 1\pmod{n_{k}}, niin  x\equiv a_{k}\pmod{n_{k}} . Siis x on kongruenssiryhmän ratkaisu.
 
Todistetaan, että ratkaisu on yksikäsitteinen modulo N. Olkoot x_{0} ja x_{1} kaksi kongruenssiryhmän ratkaisua. Silloin jokaista lukua k=1,2,...,r  kohti on  x_{0}\equiv x_{1}\equiv a_{k}\pmod{n_{k}} , joten jokaista lukua k=1,2,...,r  kohti n_{k}\mid (x_{0}-x_{1}). Näin ollen N \mid(x_{0}-x_{1}) eli   x_{0}\equiv x_{1}\pmod{N}.

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

x=a_1b_1\frac{N}{n_1}+\ldots+a_kb_k\frac{N}{n_k} \pmod{N},

missä kertoimet b_i saadaan ratkaistua yhtälöstä

b_i\frac{N}{n_i}\equiv 1 \pmod{n_i}.

## 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ä:

:\begin{align}
 x &\equiv 2 \pmod{3} \\
 x &\equiv 3 \pmod{5} \\
 x &\equiv 2 \pmod{7}
\end{align}
Luvut 3, 5 ja 7 ovat pareittain jaottomia keskenään, joten voimme soveltaa kiinalaista jäännöslausetta. Nyt N=3\cdot 5 \cdot 7=105. Ratkaistaan ensin kertoimet b_i:

b_1\frac{105}{3}\equiv 1 \pmod{3}\qquad b_2\frac{105}{5}\equiv 1 \pmod{5} \qquad b_3\frac{105}{7}\equiv 1 \pmod{7}

Kokeilemalla ratkeaa b_1=2, b_2=1, b_3=1. Sotilaiden määräksi saadaan:

x=2\cdot 2\frac{105}{3}+3\cdot 1\frac{105}{5}+2\cdot 1\frac{105}{7}=233 \pmod{105}.

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