Chinese reststelling

In de getaltheorie, een deelgebied van de wiskunde, bepaalt de Chinese reststelling een getal dat voor elk van een aantal gegeven delers die onderling relatief priem zijn, bij deling daardoor een gegeven rest achterlaat.

Meer formeel zegt de stelling dat een stelsel congruentievergelijkingen in het gehele getal :

voor delers die relatief priem zijn, een oplossing heeft. De stelling geeft ook aan hoe de oplossing gevonden kan worden.

Wat is bijvoorbeeld het kleinste getal dat bij deling door 3 een rest 2 heeft, bij deling door 5 een rest 3 en ten slotte bij deling door 7 een rest 2 heeft? Het antwoord is 23.

Geschiedenis

bewerken

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

bewerken

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  .[1]

Voorbeeld

bewerken

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.