Lähdekoodi sivulle Kiinalainen jäännöslause

{{viitteetön}}'''Kiinalainen jäännöslause''' on matematiikassa [[lukuteoria]]an, tarkemmin sanottuna [[kongruenssi (lukuteoria)|kongruensseihin]] liittyvä tulos.
== Teoreema ==
Teoreeman julkaisi ensimmäisen kerran [[Kiina|kiinalainen]] matemaatikko [[Sun Tzu (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 [[Fibonacci]]n kirjassa [[Liber Abaci]] ([[1202]]). 

Olkoot ''n''<sub>1</sub>, ''n''<sub>2</sub>, …, ''n''<sub>''k''</sub> positiivisia [[kokonaisluku]]ja jotka ovat pareittain [[keskenään jaottomat luvut|keskenään jaottomia]]. Silloin mille tahansa kokonaisluvuille ''a''<sub>1</sub>,''a''<sub>2</sub>, …, ''a''<sub>''k''</sub>, on olemassa kokonaisluku ''x'' joka ratkaisee kongruenssiyhtälöryhmän

:<math>\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}</math>

Lisäksi kaikki ratkaisut ''x'' ovat kongruentteja modulo ''N'', missä ''N'' = ''n''<sub>1</sub>''n''<sub>2</sub>…''n''<sub>''k''</sub>.


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


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

:<math>a_i \equiv a_j \pmod{{pyj}(n_i,n_j)} \qquad \mbox{kaikilla }i\mbox{ ja }j . \,\! </math>

Kaikki ratkaisut ''x'' ovat siten kongruentteja modulo pienin yhteinen jaettava (pyj) ''n<sub>i</sub>''.


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

Kokonaislukujen modulo <math>n </math> [[Rengas (matematiikka)|rengas]] <math>\mathbb{Z}/n\mathbb{Z}</math> ,jossa <math>n </math> voidaan kirjoittaa alkulukujen tulona seuraavasti <math>n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}</math>. 

Kun <math>p_i</math>:t ovat eri alkulukuja, niin rengas <math>\mathbb{Z}/n\mathbb{Z}</math> on luonnollisesti [[isoformismi|isomorfinen]] tulorenkaan <math>\mathbb{Z}/p_1^{r_1}\mathbb{Z} \times \mathbb{Z}/p_2^{r_2}\mathbb{Z} \times \cdots \times \mathbb{Z}/p_k^{r_k}\mathbb{Z}</math> 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 <big><math>N_{k}=N/n_{k}=n_{1}n_{2}...n_{k-1}n_{k}...n_{r}</math></big>. Koska luvut <math> n_{1}, n_{2},...,n_{r}</math> ovat pareittain suhteellisia alkulukuja, niin <big><math>syt(N_{k},n_{k})=1</math></big>. Näin ollen luvulla <math>N_{k}</math> on käänteisluku modulo <math>n_{k}</math>. Merkitään tätä käänteislukua symbolilla <math>b_{k}</math>, jolloin <math>N_{k}b_{k}\equiv 1\pmod{n_{k}}</math>.

Nyt voimme muodostaa summan

<big><math> x=a_{1}N_{1}b_{1}+a_{2}N_{2}b_{2}+...+a_{r}N_{r}b_{r}</math></big>.

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

== Ratkaisukaava ==
Kun <math>n_i</math>:t ovat pareittain suhteellisia alkulukuja voidaan kongruenssiyhtälöryhmä ratkaista seuraavan kaavan avulla:

<math>x=a_1b_1\frac{N}{n_1}+\ldots+a_kb_k\frac{N}{n_k} \pmod{N}</math>,

missä kertoimet <math>b_i</math> saadaan ratkaistua yhtälöstä

<math>b_i\frac{N}{n_i}\equiv 1 \pmod{n_i}</math>.

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

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

<math>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}</math>

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

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

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

== Lähteet ==
* {{Kirjaviite | Tekijä = Rosen, Kenneth H. | Nimeke = Elementary Number Theory and Its Applications | Vuosi = 1984 | Julkaisija = Addison-Wesley | Julkaisupaikka = Reading, Massachusetts | Isbn = 0-201-06561-4 | Kieli = {{en}} | Sivut = 107–109}}

== Aiheesta muualla ==

* [http://web.archive.org/web/20050829235348/http://mtl.uta.fi/Opetus/Lukuteoria/Harjoitukset/kiinalainen.pdf Kiinalainen jäännöslause ja sen sovelluksia]
* [http://mathworld.wolfram.com/ChineseRemainderTheorem.html Kiinalainen jäännöslause MathWorldissa] (englanniksi)
* http://solmu.math.helsinki.fi/2012/3/kiinalainen.pdf

[[Luokka: Lukuteoria]]
[[Luokka:Matemaattiset teoreemat]]