Kiinalainen jäännöslause

Tähän artikkeliin tai sen osaan on merkitty lähteitä, mutta niihin ei viitata. Älä poista mallinetta ennen kuin viitteet on lisätty. Voit auttaa Wikipediaa lisäämällä artikkelille asianmukaisia viitteitä. Lähteettömät tiedot voidaan kyseenalaistaa tai poistaa.

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

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

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

Lisäksi kaikki ratkaisut x ovat kongruentteja modulo N, missä N = n₁n₂…n_k.

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

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

${\displaystyle a_{i}\equiv a_{j}{\pmod {{pyj}(n_{i},n_{j})}}\qquad {\mbox{kaikilla }}i{\mbox{ ja }}j.\,\!}$

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

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

Kokonaislukujen modulo ${\displaystyle n}$ rengas ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ,jossa ${\displaystyle n}$ voidaan kirjoittaa alkulukujen tulona seuraavasti ${\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}$.

Kun ${\displaystyle p_{i}}$:t ovat eri alkulukuja, niin rengas ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ on luonnollisesti isomorfinen tulorenkaan ${\displaystyle \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} }$ kanssa.

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 ${\displaystyle N_{k}=N/n_{k}=n_{1}n_{2}...n_{k-1}n_{k}...n_{r}}$. Koska luvut ${\displaystyle n_{1},n_{2},...,n_{r}}$ ovat pareittain suhteellisia alkulukuja, niin ${\displaystyle syt(N_{k},n_{k})=1}$. Näin ollen luvulla ${\displaystyle N_{k}}$ on käänteisluku modulo ${\displaystyle n_{k}}$. Merkitään tätä käänteislukua symbolilla ${\displaystyle b_{k}}$, jolloin ${\displaystyle N_{k}b_{k}\equiv 1{\pmod {n_{k}}}}$.

Nyt voimme muodostaa summan

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

Osoitetaan nyt, että kokonaisluku ${\displaystyle x}$ on kongruenssiryhmän ratkaisu. Tehdään tämä osoittamalla, että ${\displaystyle x\equiv a_{k}{\pmod {n_{k}}}}$ kaikilla ${\displaystyle k=1,2,...,r}$. Koska ${\displaystyle n_{j}\mid N_{k}}$, kun ${\displaystyle j\neq k}$, niin ${\displaystyle N_{j}\equiv 0{\pmod {n_{k}}}}$. Näin ollen, ${\displaystyle x\equiv a_{k}N_{k}b_{k}\equiv a_{k}{\pmod {n_{k}}}}$. Koska ${\displaystyle N_{k}b_{k}\equiv 1{\pmod {n_{k}}}}$, niin ${\displaystyle x\equiv a_{k}{\pmod {n_{k}}}}$. Siis ${\displaystyle x}$ on kongruenssiryhmän ratkaisu.

Todistetaan, että ratkaisu on yksikäsitteinen modulo ${\displaystyle N}$. Olkoot ${\displaystyle x_{0}}$ ja ${\displaystyle x_{1}}$ kaksi kongruenssiryhmän ratkaisua. Silloin jokaista lukua ${\displaystyle k=1,2,...,r}$ kohti on ${\displaystyle x_{0}\equiv x_{1}\equiv a_{k}{\pmod {n_{k}}}}$, joten jokaista lukua ${\displaystyle k=1,2,...,r}$ kohti ${\displaystyle n_{k}\mid (x_{0}-x_{1})}$. Näin ollen ${\displaystyle N\mid (x_{0}-x_{1})}$ eli ${\displaystyle x_{0}\equiv x_{1}{\pmod {N}}}$.

Kun ${\displaystyle n_{i}}$:t ovat pareittain suhteellisia alkulukuja voidaan kongruenssiyhtälöryhmä ratkaista seuraavan kaavan avulla:

${\displaystyle x=a_{1}b_{1}{\frac {N}{n_{1}}}+\ldots +a_{k}b_{k}{\frac {N}{n_{k}}}{\pmod {N}}}$,

missä kertoimet ${\displaystyle b_{i}}$ saadaan ratkaistua yhtälöstä

${\displaystyle b_{i}{\frac {N}{n_{i}}}\equiv 1{\pmod {n_{i}}}}$.

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

${\displaystyle {\begin{aligned}x&\equiv 2{\pmod {3}}\\x&\equiv 3{\pmod {5}}\\x&\equiv 2{\pmod {7}}\end{aligned}}}$

Luvut 3, 5 ja 7 ovat pareittain jaottomia keskenään, joten voimme soveltaa kiinalaista jäännöslausetta. Nyt ${\displaystyle N=3\cdot 5\cdot 7=105}$. Ratkaistaan ensin kertoimet ${\displaystyle b_{i}}$:

${\displaystyle 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 ${\displaystyle b_{1}=2}$, ${\displaystyle b_{2}=1}$, ${\displaystyle b_{3}=1}$. Sotilaiden määräksi saadaan:

${\displaystyle 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, ...

• Rosen, Kenneth H.: Elementary Number Theory and Its Applications, s. 107–109. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)

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