Kinesiska restklassatsen

Från Wikipedia
Hoppa till: navigering, sök

Kinesiska restklassatsen (eller Kinesiska restsatsen) inom talteorin säger 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.

Exempel[redigera | redigera wikitext]

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 , så vi tar (mod 3), (mod 7), (mod 10). Då är alltså enligt ovan

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[redigera | redigera wikitext]

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 "vanliga" diofantiska ekvationer[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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:

,

ä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[redigera | redigera wikitext]

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