Kinesiska restklassatsen

Kinesiska restklassatsen (eller Kinesiska restsatsen) inom talteorin säger att om heltalen $n_{1},\ldots ,n_{k}$ är parvis relativt prima och $a_{1},a_{2},\ldots ,a_{k}$ är givna heltal har kongruenssystemet:

${\begin{array}{lcl}x&\equiv &a_{1}\;(\mathrm {mod} \;n_{1})\\x&\equiv &a_{2}\;(\mathrm {mod} \;n_{2})\\&\vdots &\\x&\equiv &a_{k}\;(\mathrm {mod} \;n_{k})\\\end{array}}$

en unik lösning modulo $N=n_{1}n_{2}\ldots n_{k}$.

En lösning till kongruenssystemet ges av

$x=\sum _{i=1}^{k}a_{i}b_{i}(N/n_{i})$

om varje $b_{i}$ är en lösning till kongruensen

$b_{i}(N/n_{i})\equiv 1\;(\mathrm {mod} \;n_{i}).$

Enligt Eulers sats kan man, om $n_{i}>1$, exempelvis ta $b_{i}\equiv (N/n_{i})^{\varphi (n_{i})-1}$ (mod $n_{i}$), där $\varphi$ är Eulers fi-funktion.

Exempel

Jag tänker på ett tal. Om jag delar det med 3 får jag resten 2. Om jag delar det med 7 får jag resten 3. Om jag delar det med 10 får jag resten 3. Vilket är talet?

Vi formulerar problemet som ett kongruenssystem:

${\begin{array}{lcl}x&\equiv &2\;(\mathrm {mod} \;3)\\x&\equiv &3\;(\mathrm {mod} \;7)\\x&\equiv &3\;(\mathrm {mod} \;10)\\\end{array}}$

Eftersom 3, 7, 10 är parvis relativt prima säger kinesiska restsatsen att det finns en unik lösning modulo deras produkt, det vill säga 210. Vi har $\varphi (3)=2,\ \varphi (7)=6,\ \varphi (10)=4$, så vi tar $b_{1}\equiv 70^{1}\equiv 1$ (mod 3), $b_{2}\equiv 30^{5}\equiv 2^{5}=8\cdot 4\equiv 4$ (mod 7), $b_{3}\equiv 21^{3}\equiv 1$ (mod 10). Då är alltså enligt ovan

$x=2\cdot 1\cdot 70+3\cdot 4\cdot 30+3\cdot 1\cdot 21=563$

en lösning. Men lösningen är inte unik: genom att lägga på multipler av 210 får vi nya lösningar. Exempelvis är $563-2\cdot 210=143$ en lösning. Enligt satsen får vi alla lösningar genom att lägga på multipler av 210, så 143 är den minsta positiva lösningen.

Externa länkar

http://solmu.math.helsinki.fi/2012/3/kiinalainen.pdf