Kinesiska restklassatsen

Enligt Kinesiska restklassatsen (eller Kinesiska restsatsen) inom talteorin innebär att om heltalen  är parvis relativt prima och  är givna heltal så har kongruenssystemet:

en unik lösning modulo . 

En lösning till kongruenssystemet ges av

om varje  är en lösning till kongruensen

Enligt Eulers sats kan man, om , exempelvis ta  (mod ), där  ä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:

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 , beräknas med   , , .  då  med resten 2. Då är alltså enligt ,

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  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  ä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() är 1 för varje val av i och j sådana att . Detta är ekvivalent 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  skilda från 0. I så fall är för varje  produkten av alla de övriga k-1 många talen lika med kvoten , där N är produkten av alla de k talen. I exemplet ovan är , ,  och . Därför blir , , , och . 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 .
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

är också en lösning till bara de två första kongruenserna. Den första kongruensen är ekvivalent med att det finns ett heltal , sådant att . På samma sätt motsvarar den andra kongruensen att  . Detta ger den vanliga diofantiska ekvationen , där ,  och  är kända konstanter, och  och  ä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  för något heltal  Man kan nu på samma sätt behandla denna kongruens och den tredje ursprungliga kongruensen (alltså ) som en vanlig diofantisk ekvation, och ersätta dessa två kongruenser med en enda kongruens . 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

ger de två första kongruenserna den diofantiska ekvationen . Denna kan på vanligt sätt lösas genom att man utför Euklides algoritm, först framlänges:

och sedan baklänges:
,
så  är en lösning, och  () är den allmänna lösningen. Detta ger

eller med andra ord . I nästa rekursionssteg kombineras detta med , vilket ger den diofantiska ekvationen , Euklides algoritm fram- och baklänges ger

respektive
,
vilket uppmultiplicerat med 7 ger att  är en lösning, och  den allmänna lösningen. Detta ger slutligen
,
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

Modulär aritmetik
Kommutativ algebra
Satser inom talteori