Chinese reststelling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de getaltheorie, een deelgebied van de wiskunde, bepaalt de Chinese reststelling een getal n 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 de Chinese wiskundige Sunzi (孫子) in zijn Sunzi Suanjing (孫子算經, het 'rekenkundig handboek van Meester Sun'). De stelling werd opnieuw in 1247 gepubliceerd, nu door de Chinese wiskundige Qin Jiushao, in zijn "Wiskundige verhandeling in negen secties".

Principe[bewerken]

Laat positieve gehele getallen zijn die paarsgewijs relatief priem zijn (wat wil zeggen dat geen tweetal een gemeenschappelijke deler heeft anders dan 1). Dan geldt voor elk -tal gehele getallen , dat er een geheel getal bestaat dat oplossing is van het systeem van simultane congruenties:

Bovendien zijn alle oplossingen van dit systeem onderling congruent modulo het product .

Een oplossing wordt als volgt gevonden. Voor elke zijn de gehele getallen en relatief priem, zodat er, gebruikmakend van (een uitbreiding van) het Euclidische algoritme gehele getallen en te vinden zijn, waarvoor geldt:

Noem nu , dan is: en voor alle .

Het getal vormt dan de gevraagde oplossing van het systeem van simultane congruenties.

Voorbeeld[bewerken]

Beschouw bij wijze van voorbeeld het vraagstuk dat een geheel getal x wordt gezocht waarvoor geldt dat

,

dat wil zeggen zoek een getal (bedoeld wordt: het kleinste getal) dat bij deling door 3 een rest van 2 overlaat, bij deling door 4 een rest van 3 en bij deling door 5 een rest van 2.

Toepassen van (een uitbreiding van) het Euclidische algoritme voor 3 en 4 x 5 = 20, levert op (-13) x 3 + 2 x 20 = 1 (). Toepassen van het Euclidische algoritme voor 4 en 3 x 5 = 15, levert op (-11) x 4 + 3 x 15 = 1 (). En toepassing van het Euclidische algoritme voor 5 en 3 x 4 = 12, geeft 5 x 5 + (-2) x 12 = 1 (). Een oplossing x is daarom bijvoorbeeld 2 x 40 + 3 x 45 + 2 x (-24) = 167. Alle andere oplossingen zijn congruent met 167 modulo 60, en dus alle congruent met 47 modulo 60, m.a.w. het gezochte getal is 47.

Merk op dat sommige systemen van de vorm (1) zelfs oplosbaar zijn wanneer de getallen ni niet paarsgewijs relatief priem zijn. Het exacte criterium is als volgt: er bestaat een oplossing x dan en slechts dan als ai aj (mod ggd(ni, nj)) voor alle i en j. Alle oplossingen x zijn congruent modulo het kleinste gemene veelvoud van de ni.

Externe link[bewerken]