In de getaltheorie, een deelgebied van de wiskunde, bepaalt de Chinese reststelling een getal , dat gedeeld door elk van een aantal gegeven delers die paarsgewijs relatief priem zijn, een gegeven rest achterlaat.
Een stelsel congruentievergelijkingen voor delers die relatief priem zijn:
dus in één gehele onbekende , heeft volgens de stelling een oplossing voor . De stelling geeft ook aan hoe de oplossing kan worden gevonden.
23 is bijvoorbeeld het kleinste getal dat bij delen door 3 een rest 2 heeft, bij delen door 5 een rest 3 en ten slotte bij delen door 7 een rest 2 heeft.
Geschiedenis De stelling werd voor het eerst beschreven in de vierde eeuw na Chr. door Sunzi (孫子) in zijn Sunzi Suanjing (孫子算經), het 'rekenkundig handboek van Meester Sun'. De stelling werd opnieuw in 1247 gepubliceerd, nu door Qin Jiushao, in zijn Wiskundige verhandeling in negen secties. Beiden waren wiskundige uit de tijd van het Chinese Keizerrijk, dat duurde van 221 v.Chr. tot 1911.
Principe Laat positieve gehele getallen zijn die paarsgewijs relatief priem zijn, wat wil zeggen dat de grootste gemene deler van ieder tweetal daarvan 1 is. Dan is er voor elk -tal gehele getallen een geheel getal dat een oplossing is van het stelsel van simultane congruenties:
Alle oplossingen zijn congruent modulo het kleinste gemene veelvoud van de .
Een oplossing wordt gevonden door steeds twee congruenties tot een congruentie samen te voegen.
waarin en relatief priem zijn.
Er zijn dan volgens de stelling van Bachet-Bézout twee gehele getallen en zodat .
Hierin kunnen en met het uitgebreide algoritme van Euclides worden berekend. Er is dus een oplossing . Inderdaad is ,
waaruit volgt dat
Evenzo is ,
waaruit volgt dat
Dit geeft samen de nieuwe congruentie
Het stelsel van congruenties is hierdoor gereduceerd tot een stelsel van congruenties. Er kan zo worden doorgegaan totdat er een is gevonden die aan de oorspronkelijke congruenties voldoet.
Merk op dat sommige van deze stelsels zelfs een oplossing hebben als de getallen niet paarsgewijs relatief priem zijn. Het exacte criterium is: er bestaat een oplossing dan en slechts dan als voor alle en .Dezelfde methode kan dan ook worden gebruikt, behalve dat de vergelijking door moet worden vervangen en om de nieuwe te berekenen door de moet worden gedeeld.
Voorbeeld Gezocht wordt een geheel getal waarvoor geldt dat
Begin met de eerste twee congruenties. Er zijn getallen en , zodat . Hoewel een oplossing voor deze vergelijking meteen is te zien, geeft ook het uitgebreide algoritme van Euclides de oplossing en . Het getal voldoet dus aan de eerste twee congruenties en geeft de nieuwe congruentie:
Gecombineerd met
leidt dit tot het bestaan van nieuwe getallen en die voldoen aan . Het uitgebreide algoritme van Euclides geeft en . Dus voldoet aan beide congruenties en daarmee aan de drie gegeven congruenties. Een andere oplossing is bijvoorbeeld . Het algoritme kost veel rekentijd.
Categorie:Getaltheorie Categorie:Modulair rekenen