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 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 restsatsen att det finns en unik lösning modulo deras produkt, det vill säga 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.

Externa länkar[redigera | redigera wikitext]

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