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 wanneer het door een aantal gegeven delers wordt gedeeld een gegeven rest achterlaat.

Wat is bijvoorbeeld het kleinste getal n dat bij deling door 3 een rest van 2 heeft, bij deling door 5 een rest van 3 heeft en ten slotte bij deling door 7 een rest van 2 heeft? Een bekend inleidend voorbeeld is een vrouw die een politieman vertelt dat zij haar mandje met eieren heeft verloren; als zij er elke keer drie uithaalde, hield zij er 2 over. Wanneer zij er vijf tegelijk uithaalde hield zij er drie over en wanneer er zij zeven tegelijk uithaalde hield zij er twee over. Vervolgens vraagt zij de politieman wat het minimum aantal eieren was in haar eiermandje zat. Het antwoord op beide problemen 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]

Stel dat n1, ..., nk positieve gehele getallen zijn, die paarsgewijs relatief priem zijn (dat wil zeggen dat ggd(ni, nj) = 1 voor alle i en j met i \neq j). Dan geldt voor elke willekeurige gegeven verzameling gehele getallen {a1, ..., ak}, dat er een geheel getal x bestaat dat oplossing is van het volgende systeem van simultane congruenties: x \equiv a_i (mod n_i) voor i = 1 \ldots k (1)

Bovendien zijn alle oplossingen x van dit systeem onderling congruent modulo het product n = n_1 \cdot \ldots \cdot n_k.

Een oplossing x kan als volgt worden gevonden. Voor alle i, zijn de gehele getallen ni en n/ni relatief priem, en gebruik makend van (een uitbreiding van) het Euclidische algoritme zijn er gehele getallen r en s te vinden zodanig dat r ni + s n/ni = 1. Als we nu invoeren ei = s n/ni, dan volgt: e_i \equiv 1 (mod n_i) en e_i \equiv 0 (mod n_j) voor alle j \neq i. Het getal x = \sum_{i=1}^{k} a_i e_i vormt dan een oplossing van het systeem (1) van simultane congruenties.

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

x \equiv 2 (mod 3)
x \equiv 3 (mod 4)
x \equiv 2 (mod 5),

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 (e_1 = 40). Toepassen van het Euclidische algoritme voor 4 en 3 x 5 = 15, levert op (-11) x 4 + 3 x 15 = 1 (e_2 = 45). En toepassing van het Euclidische algoritme voor 5 en 3 x 4 = 12, geeft 5 x 5 + (-2) x 12 = 1 (e_3 = -24). 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 \equiv 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]