Kinesiska restklassatsen

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-06) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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

${\displaystyle {\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 ${\displaystyle N=n_{1}n_{2}\ldots n_{k}}$.

En lösning till kongruenssystemet ges av

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

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

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

Enligt Eulers sats kan man, om ${\displaystyle n_{i}>1}$, exempelvis ta ${\displaystyle b_{i}\equiv (N/n_{i})^{\varphi (n_{i})-1}}$ (mod ${\displaystyle n_{i}}$), där ${\displaystyle \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:

${\displaystyle {\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 ${\displaystyle \varphi (3)=2,\ \varphi (7)=6,\ \varphi (10)=4}$, ${\displaystyle b_{1},b_{2},b_{3}}$beräknas med ${\displaystyle b_{i}\equiv (N/n_{i})^{\varphi (n_{i})-1}}$ ${\displaystyle b_{1}\equiv 70^{1}\equiv 1{\pmod {3}}}$, ${\displaystyle b_{2}\equiv 30^{5}\equiv 2^{5}=8\cdot 4\equiv 4{\pmod {7}}}$, ${\displaystyle b_{3}\equiv 21^{3}\equiv 1{\pmod {10}}}$. ${\displaystyle b_{2}\equiv 30^{5}\equiv 2^{5}}$ då ${\displaystyle {\frac {30}{7}}=4}$ med resten 2. Då är alltså enligt ${\displaystyle x=\sum _{i=1}^{k}a_{i}b_{i}(N/n_{i})}$,

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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(${\displaystyle n_{i},n_{j}}$) är 1 för varje val av i och j sådana att ${\displaystyle 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 ${\displaystyle n_{1},\ldots ,n_{k}}$ skilda från 0. I så fall är för varje ${\displaystyle n_{i}}$ produkten av alla de övriga k-1 många talen lika med kvoten ${\displaystyle N/n_{i}}$, där N är produkten av alla de k talen. I exemplet ovan är ${\displaystyle k=3}$, ${\displaystyle n_{1}=3}$, ${\displaystyle n_{2}=7}$ och ${\displaystyle n_{3}=10}$. Därför blir ${\displaystyle N=3\cdot 7\cdot 10=210}$, ${\displaystyle N/n_{1}=210/3=70=7\cdot 10}$, ${\displaystyle N/n_{2}=210/7=30=3\cdot 10}$, och ${\displaystyle 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 ${\displaystyle 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

${\displaystyle {\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 ${\displaystyle y_{1}}$, sådant att ${\displaystyle x=a_{1}+y_{1}\cdot n_{1}}$. På samma sätt motsvarar den andra kongruensen att ${\displaystyle x=a_{2}+y_{2}\cdot n_{2}}$. Detta ger den vanliga diofantiska ekvationen ${\displaystyle n_{1}y_{1}-n_{2}y_{2}=a_{2}-a_{1}}$, där ${\displaystyle n_{1}}$, ${\displaystyle n_{2}}$ och ${\displaystyle a_{2}-a_{1}}$ är kända konstanter, och ${\displaystyle y_{1}}$ och ${\displaystyle 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 ${\displaystyle x\equiv b_{1}{\pmod {n_{1}n_{2}}}}$ för något heltal ${\displaystyle b_{1}}$ Man kan nu på samma sätt behandla denna kongruens och den tredje ursprungliga kongruensen (alltså ${\displaystyle x\equiv a_{3}{\pmod {n_{3}}}}$) som en vanlig diofantisk ekvation, och ersätta dessa två kongruenser med en enda kongruens ${\displaystyle 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

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

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

och sedan baklänges:

${\displaystyle 1=7-2\cdot 3=3\cdot (-2)-7\cdot (-1)}$,

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

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

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

${\displaystyle {\begin{array}{lcrcl}21&=&2\cdot 10&+&1\\\end{array}}}$

respektive

${\displaystyle 1=21-2\cdot 10=1\cdot 21-2\cdot 10}$,

vilket uppmultiplicerat med 7 ger att ${\displaystyle (k,y_{3})=(7,14)}$ är en lösning, och ${\displaystyle (k,y_{3})=(7+10t,14-21t)}$ den allmänna lösningen. Detta ger slutligen

${\displaystyle x=-4+21k=-4+21(7+10t)=143+210t}$,

vilket på grund av uniciteten mycket riktigt är samma lösning som den första metoden gav.

Externa länkar

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