Chinese reststelling

In de getaltheorie, een deelgebied van de wiskunde, bepaalt de Chinese reststelling een getal $x$ 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 $x$:

$x\equiv r_i{modd}_i,i=1,\dots ,n$

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

Wat is bijvoorbeeld het kleinste getal $x$ 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

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 $n_1,\dots ,n_k$ 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 $k$-tal gehele getallen $a_1,\dots ,a_k$ een geheel getal $x$ dat een oplossing is van het stelsel van simultane congruenties:

$x\equiv a_i{modn}_i,i=1,\dots ,k$

Alle oplossingen $x$ zijn congruent modulo het kleinste gemene veelvoud van de $n_i$.

Een oplossing $x$ wordt gevonden door steeds twee congruenties tot een congruentie samen te voegen.

$\begin{array}{cc}x& \equiv a_1{modn}_1\\ x& \equiv a_2{modn}_2,\end{array}$

waarin $n_1$ en $n_2$ relatief priem zijn.

Er zijn dan volgens de stelling van Bachet-Bézout twee gehele getallen $m_1$ en $m_2$ zodat

$m_1{n}_1+m_2{n}_2=1$.

Hierin kunnen $m_1$ en $m_2$ met het uitgebreide algoritme van Euclides worden berekend. Er is dus een oplossing $x=a_1{m}_2{n}_2+a_2{m}_1{n}_1$. Inderdaad is

$x=a_1{m}_2{n}_2+a_2{m}_1{n}_1=a_1(1-m_1{n}_1)+a_2{m}_1{n}_1=a_1+(a_2-a_1)m_1{n}_1$,

waaruit volgt dat

$x\equiv a_1{modn}_1$

Evenzo is

$x=a_2+(a_1-a_2)m_2{n}_2$,

waaruit volgt dat

$x\equiv a_2{modn}_2$

Dit geeft samen de nieuwe congruentie

$x=a_1{m}_2{n}_2+a_2{m}_1{n}_1{modn}_1{n}_2$

Het stelsel van $k$ congruenties is hierdoor gereduceerd tot een stelsel van $k-1$ congruenties. Er kan zo worden doorgegaan totdat er een $x$ is gevonden die aan de $k$ oorspronkelijke congruenties voldoet.

Merk op dat sommige van deze stelsels zelfs een oplossing hebben als de getallen $n_i$ niet paarsgewijs relatief priem zijn. Het exacte criterium is: er bestaat een oplossing $x$ dan en slechts dan als $a_i\equiv a_{j}mod\mathrm{ggd}(n_i,n_j)$ voor alle $i$ en $j$.

Voorbeeld

Gezocht wordt een geheel getal $x$ waarvoor geldt dat

$x\equiv 2mod3$

$x\equiv 3mod4$

$x\equiv 2mod5$

Begin met de eerste twee congruenties. Er zijn getallen $m_1$ en $m_2$, zodat $m_{1}3+m_{2}4=1$. Hoewel een oplossing voor deze vergelijking meteen is te zien, geeft ook het uitgebreide algoritme van Euclides de oplossing $m_1=-1$ en $m_2=1$. Het getal $x=a_1{m}_2{n}_2+a_2{m}_1{n}_1=-1$ voldoet dus aan de eerste twee congruenties en geeft de nieuwe congruentie:

$x\equiv -1mod12$

Gecombineerd met

$x\equiv 2mod5$

leidt dit tot het bestaan van nieuwe getallen $m_1$ en $m_2$ die voldoen aan $m_{1}12+m_{2}5=1$. Het uitgebreide algoritme van Euclides geeft $m_1=-2$ en $m_2=5$. Dus voldoet $x=a_1{m}_2{n}_2+a_2{m}_1{n}_1=-73$ aan beide congruenties, en daarmee aan de drie gegeven congruenties. Een andere oplossing is bijvoorbeeld $-73+2\cdot (3\cdot 4\cdot 5)=-73+120=47$. Het algoritme kost veel rekentijd.