Kinesiska restklassatsen

Sun-tzu's ursprungliga formulering: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) med lösningen x = 23 + 105k, där k är ett heltal

Enligt Kinesiska restklassatsen (eller Kinesiska restsatsen) inom talteorin innebär att om heltalen $n_{1},\ldots ,n_{k}$ är parvis relativt prima och $a_{1},a_{2},\ldots ,a_{k}$ är givna heltal så 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.

Det första kända omnämnandet av satsen gjordes av den kinesiske matematikern Sun-tzu i verket Sun-tzu Suan-ching under 200-talet e.Kr.

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 restklassatsen att det finns en lösning, och att denna är unik modulo deras produkt, det vill säga modulo 210. Vi har $\varphi (3)=2,\ \varphi (7)=6,\ \varphi (10)=4$ , $b_{1},b_{2},b_{3}$ beräknas med $b_{i}\equiv (N/n_{i})^{\varphi (n_{i})-1}$ $b_{1}\equiv 70^{1}\equiv 1{\pmod {3}}$ , $b_{2}\equiv 30^{5}\equiv 2^{5}=8\cdot 4\equiv 4{\pmod {7}}$ , $b_{3}\equiv 21^{3}\equiv 1{\pmod {10}}$ . $b_{2}\equiv 30^{5}\equiv 2^{5}$ då ${\frac {30}{7}}=4$ med resten 2. Då är alltså enligt $x=\sum _{i=1}^{k}a_{i}b_{i}(N/n_{i})$ ,

x=\sum _{i=1}^{3}a_{i}b_{i}(210/n_{i})=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.

Detaljförklaringar

Att heltalen $n_{1},\ldots ,n_{k}$ är parvis relativt prima betyder att varje tänkbart urval av två av dessa är relativt prima, alltså att den största gemensamma delaren SGD( $n_{i},n_{j}$ ) är 1 för varje val av i och j sådana att $1\leq i<j\leq k$ . Detta är ekvivalent^{[särskiljning behövs]} med att inget enda av de k talen innehåller någon primtalsfaktor som något annat av talen innehåller.

I de intressanta tillämpningarna är också antalet k minst 2, och alla talen $n_{1},\ldots ,n_{k}$ skilda från 0. I så fall är för varje $n_{i}$ produkten av alla de övriga k-1 många talen lika med kvoten $N/n_{i}$ , där N är produkten av alla de k talen. I exemplet ovan är $k=3$ , $n_{1}=3$ , $n_{2}=7$ och $n_{3}=10$ . Därför blir $N=3\cdot 7\cdot 10=210$ , $N/n_{1}=210/3=70=7\cdot 10$ , $N/n_{2}=210/7=30=3\cdot 10$ , och $N/n_{1}=210/10=21=3\cdot 7$ . I praktiken är det oftast lättare att räkna ut dessa tal som produkter än som kvoter.

Satsen säger att en unik lösning existerar modulo N. Det betyder att systemet har många lösningar, men att alla lösningar är kongruenta modulo N, eller med andra ord bara skiljer sig åt med multiplar av N. En lösning presenteras också i form av ett ofta litet svårberäknat uttryck, där man behöver lösa ett antal kongruenser modulo de olika $N/n_{i}$ . I exemplet användes Eulers fi-funktion för att lösa dessa kongruenser. En fördel med att använda just detta uttryck för lösningen är att det går rätt lätt att teoretiskt bevisa att detta verkligen löser det ursprungliga kongruenssystemet. Rent räknemässigt är dock det ofta lättare att använda Euklides algoritm rekursivt, för att i varje rekursionssteg lösa en diofantisk ekvation av standardtyp.

Omformulering som k-1 "vanliga" diofantiska ekvationer

Varje lösning till kongruenssystemet

{\begin{array}{lcl}x&\equiv &a_{1}\;{\pmod {n_{1}}}\\x&\equiv &a_{2}\;{\pmod {n_{2}}}\\&\vdots &\\x&\equiv &a_{k}\;{\pmod {n_{k}}}\\\end{array}}

är också en lösning till bara de två första kongruenserna. Den första kongruensen är ekvivalent med att det finns ett heltal $y_{1}$ , sådant att $x=a_{1}+y_{1}\cdot n_{1}$ . På samma sätt motsvarar den andra kongruensen att $x=a_{2}+y_{2}\cdot n_{2}$ . Detta ger den vanliga diofantiska ekvationen $n_{1}y_{1}-n_{2}y_{2}=a_{2}-a_{1}$ , där $n_{1}$ , $n_{2}$ och $a_{2}-a_{1}$ är kända konstanter, och $y_{1}$ och $y_{2}$ är obekanta heltal. Om man löser denna ekvation på vanligt sätt, och använder denna lösning för att beskriva x, så får man att de två första kongruenserna uppfylls precis om $x\equiv b_{1}{\pmod {n_{1}n_{2}}}$ för något heltal $b_{1}$ Man kan nu på samma sätt behandla denna kongruens och den tredje ursprungliga kongruensen (alltså $x\equiv a_{3}{\pmod {n_{3}}}$ ) som en vanlig diofantisk ekvation, och ersätta dessa två kongruenser med en enda kongruens $x\equiv b_{2}{\pmod {n_{1}n_{2}n_{3}}}$ . På detta sätt kan man fortsätta att ersätta två gamla kongruenser med en ny, tills man har reducerat hela systemet till en enda kongruens modulo N.

Tillämpning i det första exemplet

I exemplet

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

ger de två första kongruenserna den diofantiska ekvationen $3y_{1}-7y_{2}=3-2=1$ . Denna kan på vanligt sätt lösas genom att man utför Euklides algoritm, först framlänges:

{\begin{array}{lcrcl}7&=&2\cdot 3&+&1\\\end{array}}

och sedan baklänges:

1=7-2\cdot 3=3\cdot (-2)-7\cdot (-1)

,

så $(y_{1},y_{2})=(-2,-1)$ är en lösning, och $(y_{1},y_{2})=(-2+7k,-1+3k)$ ( $k\in {\bf {Z}}$ ) är den allmänna lösningen. Detta ger

x=2+3y_{1}=2+3(-2+7k)=-4+21k

eller med andra ord $x\equiv -4{\pmod {21}}$ . I nästa rekursionssteg kombineras detta med $x\equiv 3{\pmod {10}}$ , vilket ger den diofantiska ekvationen $21k-10y_{3}=3+4=7$ , Euklides algoritm fram- och baklänges ger