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
bewerkenDe 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
bewerkenLaat 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
bewerkenGezocht 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.
- voetnoten
- ↑ 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.
- websites
- (en) Qin Jiushao