De Chinese reststelling uitgelegd

Een getal geeft rest 2 bij deling door 3, rest 3 bij deling door 5 en rest 2 bij deling door 7. Welk getal is het? Probeer de getallen één voor één en na een tijdje kom je bij 23, maar in de vraag schuilt een stelling: zolang de delers geen gemeenschappelijke factor hebben, is er onder hun product altijd precies één antwoord, en je vindt het zonder iets te proberen. De stelling is zo'n 1.500 jaar oud en werkt nog steeds in kalenders, in het rekenen van computers en in de cryptografie die het web beschermt.

Drie rijen markeringen voor de getallen met rest 2 mod 3, 3 mod 5 en 2 mod 7, die in één kolom bij 23 samenkomen
Drie rijen markeringen voor de getallen met rest 2 mod 3, 3 mod 5 en 2 mod 7, die in één kolom bij 23 samenkomen

Een probleem uit de Sunzi Suanjing

De Sunzi Suanjing, een Chinees rekenboek uit de 3e tot 5e eeuw, vraagt naar een aantal dingen dat per drie geteld 2 overlaat, per vijf 3 en per zeven 2. Het antwoord is 23, en de methode wordt nog steeds onderwezen: neem 70 voor elk ding dat bij het tellen per drie overblijft, 21 voor elk ding bij het tellen per vijf en 15 voor elk ding bij het tellen per zeven, tel op en trek er zo vaak mogelijk 105 af. 2 × 70 + 3 × 21 + 2 × 15 = 233, en 233 − 2 × 105 = 23. Een vers uit de Ming-tijd hield de getallen 70, 21, 15 en 105 eeuwenlang in het geheugen. Qin Jiushao gaf in 1247 een algemene methode, hetzelfde probleem staat in Fibonacci's Liber Abaci van 1202, en Carl Friedrich Gauss formuleerde de stelling in 1801 in zijn Disquisitiones Arithmeticae in haar moderne vorm.

Een bladzijde uit een Qing-uitgave van de Sunzi Suanjing, het Chinese rekenboek uit de 3e–5e eeuw dat vraagt naar een getal dat bij tellen met drieën, vijven en zevenen 2, 3 en 2 overlaat.
Een bladzijde uit een Qing-uitgave van de Sunzi Suanjing, het Chinese rekenboek uit de 3e–5e eeuw dat vraagt naar een getal dat bij tellen met drieën, vijven en zevenen 2, 3 en 2 overlaat.
Carl Friedrich Gauss, op een portret van Christian Albrecht Jensen uit 1840. Hij voerde de congruentienotatie a ≡ b (mod n) in in zijn Disquisitiones Arithmeticae van 1801.
Carl Friedrich Gauss, op een portret van Christian Albrecht Jensen uit 1840. Hij voerde de congruentienotatie a ≡ b (mod n) in in zijn Disquisitiones Arithmeticae van 1801.

Wat de stelling zegt

Neem moduli n₁, n₂, …, nₖ waarvan geen twee een gemeenschappelijke factor hebben, en willekeurige resten a₁, a₂, …, aₖ. Dan is er precies één geheel getal x van 0 tot N − 1, met N = n₁ × n₂ × … × nₖ, dat bij deling door nᵢ de rest aᵢ geeft, voor elke i. Alle andere oplossingen verschillen daarvan een veelvoud van N. In de notatie van het modulair rekenen: het stelsel x ≡ aᵢ (mod nᵢ) heeft een oplossing, en die is uniek mod N. Anders gezegd dragen een getal van 0 tot N − 1 en zijn lijst van resten precies dezelfde informatie: 3 × 5 × 7 = 105 getallen en 3 × 5 × 7 = 105 mogelijke lijsten van resten, elk één keer gebruikt.

De oplossing bouwen

De getallen 70, 21 en 15 zijn geen toverij. Elk geeft rest 1 bij deling door zijn eigen modulus en rest 0 bij deling door de andere: 70 = 2 × 35 is een veelvoud van 5 en 7 en geeft rest 1 bij deling door 3. In het algemeen neem je Nᵢ = N / nᵢ, een veelvoud van elke modulus behalve nᵢ, en vermenigvuldig je dat met yᵢ, de inverse van Nᵢ mod nᵢ. De inverse bestaat omdat Nᵢ en nᵢ geen gemeenschappelijke factor hebben, en het uitgebreide algoritme van Euclides vindt haar: het voert de delingen van Euclides uit voor de grootste gemene deler en rekent terug naar de identiteit van Bézout 1 = s × nᵢ + t × Nᵢ, zodat t de inverse is. Dan past x = a₁N₁y₁ + a₂N₂y₂ + …, gereduceerd mod N, bij elke vergelijking, omdat elke term bij zijn eigen vergelijking past en in alle andere verdwijnt.

Eén vergelijking tegelijk

Er is een tweede manier, die geen product van alle moduli nodig heeft. Elke oplossing van x ≡ 2 (mod 3) heeft de vorm x = 2 + 3t. Vul dat in de volgende vergelijking in: 2 + 3t ≡ 3 (mod 5), dus 3t ≡ 1 (mod 5), en vermenigvuldigen met 2, de inverse van 3 mod 5, geeft t ≡ 2 (mod 5). Dan is x = 2 + 3 × 2 = 8, en de eerste twee vergelijkingen samen zeggen x ≡ 8 (mod 15). Herhaal dat met de derde vergelijking: 8 + 15t ≡ 2 (mod 7) geeft t ≡ 1, dus x ≡ 23 (mod 105). Deze substitutie houdt de getallen kleiner, is hoe een computer zulke stelsels meestal oplost, en werkt ook als de moduli een factor delen.

Moduli met een gemeenschappelijke factor

Als twee moduli een factor delen, overlappen hun vergelijkingen: x ≡ 1 (mod 4) zegt al dat x oneven is, en x ≡ 4 (mod 6) zegt dat x even is, dus geen enkele x voldoet aan beide. In het algemeen kunnen x ≡ a (mod m) en x ≡ b (mod n) precies dan allebei gelden als a en b dezelfde rest geven bij deling door g = gcd(m, n), dat wil zeggen als g het verschil a − b deelt. Dan is de oplossing uniek mod lcm(m, n) = m × n / g, niet mod m × n. Het oude raadsel van de mand met eieren, die er 1 overlaat als je ze per 2, 3, 4, 5 of 6 uit de mand haalt en geen per 7, heeft het antwoord 301, dat zich elke 420 = lcm(2, 3, 4, 5, 6, 7) herhaalt. Een stelsel heeft precies dan een oplossing als elk tweetal van zijn vergelijkingen klopt, dus een onoplosbaar stelsel bevat altijd een paar dat botst.

Kalenders, computers en RSA

In 1583 combineerde Joseph Scaliger drie kalendercycli, de zonnecyclus van 28 jaar, de maancyclus van 19 jaar en de indictie van 15 jaar, tot de Juliaanse periode van 28 × 19 × 15 = 7.980 jaar. Volgens de stelling heeft elk jaar zijn eigen combinatie van de drie cyclusnummers, en de periode begint in 4713 v.Chr., het laatste jaar waarin alle drie 1 waren; astronomen tellen Juliaanse dagen nog steeds vanaf dat punt. Computers gebruiken de stelling om met enorme getallen te rekenen als lijsten van kleine resten, die je apart en tegelijk kunt optellen en vermenigvuldigen en aan het eind samenvoegen. RSA-ontsleuteling werkt net zo: c^d mod n met n = p × q wordt berekend als twee machten mod p en mod q die met de stelling worden samengevoegd, ongeveer vier keer zo snel als één macht mod n. Schema's voor het delen van geheimen, zoals die van Mignotte en van Asmuth en Bloom, verbergen een geheim in resten, zodat pas genoeg ervan samen het onthullen.

Ron Rivest, Adi Shamir en Len Adleman (van links naar rechts)
Ron Rivest, Adi Shamir en Len Adleman (van links naar rechts)

Probeer het zelf

Open de calculator om een willekeurig stelsel van congruenties te typen, tot 20 vergelijkingen en getallen van hoogstens 200 cijfers, of kies een van de uitgewerkte voorbeelden: het probleem van Sunzi, de mand met eieren, de Juliaanse periode, twee busdienstregelingen, RSA-ontsleuteling en een stelsel zonder oplossing. De uitwerking staat er met jouw getallen, via de constructie of via substitutie, met het uitgebreide algoritme van Euclides voor elke inverse. De afbeelding markeert de getallen die aan elke vergelijking voldoen, zodat je de ene kolom ziet waar ze allemaal samenkomen, of zet de resten van twee vergelijkingen in een tabel waarin elk getal zijn eigen cel heeft.

Veelgestelde vragen

Is de oplossing van een stelsel van congruenties uniek?

Alleen op een veelvoud van de modulus na. Als x = 23 het probleem van Sunzi oplost, dan ook 23 + 105 = 128, 233 en −82, want 105 erbij optellen verandert geen enkele rest. De stelling zegt dat er precies één oplossing is van 0 tot 104; bij moduli met gemeenschappelijke factoren precies één onder hun kleinste gemene veelvoud.

Waarom moeten de moduli relatief priem zijn?

Voor de constructie, omdat Nᵢ een inverse mod nᵢ moet hebben, en die bestaat alleen als ze geen gemeenschappelijke factor hebben. Voor de stelling zelf, omdat gemeenschappelijke factoren sommige vergelijkingen laten overlappen: dan heeft een stelsel geen oplossing of minder verschillende, en herhalen de oplossingen zich elk kleinste gemene veelvoud in plaats van elk product.

Hoe vind ik een modulaire inverse met de hand?

Met het uitgebreide algoritme van Euclides. Voor de inverse van 15 mod 7: 15 = 2 × 7 + 1, dus 1 = 15 − 2 × 7, en 15 × 1 ≡ 1 (mod 7): de inverse is 1. Voor 35 mod 3: 35 = 11 × 3 + 2 en 3 = 1 × 2 + 1, dus 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, en de inverse van 35 mod 3 is −1 ≡ 2. Bij kleine moduli kun je ook gewoon 1, 2, 3, … proberen tot het product rest 1 geeft.

Wat heeft de stelling met klokken te maken?

Een rest mod n is een stand op een klok met n uren. Twee klokken met 3 en 5 uren, die samen starten en telkens een uur verder gaan, tonen elk van de 15 paren standen één keer voordat ze terug bij het begin zijn, omdat 3 en 5 geen gemeenschappelijke factor hebben. Klokken met 4 en 6 uren zijn na 12 stappen terug en tonen maar 12 van de 24 paren: een oneven en een even stand komen nooit samen voor.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de calculator voor de Chinese reststelling