Modulair rekenen uitgelegd

Iedereen rekent al modulair: 10 uur na 8 uur is het 6 uur, en de dag na zondag is maandag. Tellen dat na n stappen weer bij 0 begint, blijkt een eigen, volledige rekenkunde te hebben, met regels, verrassingen en een centrale plaats in de getaltheorie en in de cryptografie die het internet beveiligt.

Een klok met twaalf posities, genummerd van 0 tot 11, en een spiraalvormig pad dat één keer rond de wijzerplaat draait van 9 naar 2
Een klok met twaalf posities, genummerd van 0 tot 11, en een spiraalvormig pad dat één keer rond de wijzerplaat draait van 9 naar 2

Resten en congruentie

Deel a door n en houd alleen de rest over: dat is a mod n, een getal van 0 tot n − 1. 26 mod 7 = 5, omdat 26 = 3 × 7 + 5. Getallen met dezelfde rest gedragen zich mod n hetzelfde, dus noemen we ze congruent: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss voerde deze notatie in in zijn Disquisitiones Arithmeticae van 1801, en die maakte van de oude waarnemingen van Fermat en Euler een eigen rekenkunde. Op een klok met n posities komt elk geheel getal op zijn rest terecht; de volle rondes worden vergeten.

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.

Optellen, aftrekken en vermenigvuldigen

De drie gewone bewerkingen werken zoals altijd, en je mag mod n reduceren wanneer je wilt: de rest van een som is de rest van de som van de resten, en hetzelfde geldt voor verschillen en producten. Om het laatste cijfer van 37 × 48 te vinden, vermenigvuldig je alleen de laatste cijfers: 7 × 8 = 56, dus het eindigt op 6. Dat maakt modulair rekenen zo nuttig voor computers: hoe groot de getallen ook zijn, de tussenwaarden worden nooit groter dan n².

Delen vraagt om een inverse

Delen is de uitzondering. 2 × 3 ≡ 2 × 8 (mod 10), want beide zijn 6 mod 10, maar 3 en 8 zijn verschillend, dus je kunt de 2 niet zomaar wegstrepen. Delen door a betekent vermenigvuldigen met de inverse, het getal x met a × x ≡ 1, en die bestaat precies als a en n geen gemeenschappelijke factor hebben. Het uitgebreide algoritme van Euclides vindt hem: het voert de delingsstappen van Euclides voor de grootste gemene deler uit en houdt bij elke stap een factor bij, zodat de factor de inverse is wanneer de rest 1 bereikt. Als n priem is, heeft elk getal behalve 0 een inverse en lukt delen altijd.

Machten, Fermat en Euler

Machten herhalen zich. Neem de machten van 3 mod 7: 3, 2, 6, 4, 5, 1, en dan weer 3. De lengte van die cyclus is de orde van 3. In 1640 merkte Pierre de Fermat op dat voor een priemgetal p geldt dat a^(p − 1) ≡ 1 (mod p) wanneer p geen deler van a is, zodat elke orde een deler van p − 1 is. Leonhard Euler bewees het en breidde het uit naar elke n, met p − 1 vervangen door het aantal waarden dat relatief priem is met n. Enorme machten worden berekend door herhaald kwadrateren: a, a², a⁴, a⁸ …, elk het kwadraat van de vorige, gereduceerd mod n, en dan vermenigvuldigd volgens de binaire cijfers van de exponent.

Portret van Pierre de Fermat
Portret van Pierre de Fermat
Portret van Leonhard Euler
Portret van Leonhard Euler

Controlecijfers en kalenders

Modulair rekenen vangt fouten op. Het laatste cijfer van een ISBN-10 wordt zo gekozen dat een gewogen som van alle tien cijfers een veelvoud van 11 is, zodat elk afzonderlijk fout cijfer en elke verwisseling van twee buren wordt opgemerkt. Bankpasnummers gebruiken de Luhn-controle mod 10, en IBAN's een controle mod 97. Kalenders lopen mod 7: de weekdag van elke datum is met een paar resten uit te rekenen, en zo werken eeuwigdurende kalenders en de doomsday-regel.

Cryptografie

Moderne cryptografie is gebouwd op modulaire machten die makkelijk te berekenen en moeilijk terug te draaien zijn. Bij de Diffie–Hellman-sleuteluitwisseling van 1976 spreken twee mensen over een open lijn een gedeeld geheim af door machten modulo een groot priemgetal uit te wisselen. RSA, in 1977 gepubliceerd door Rivest, Shamir en Adleman, versleutelt een bericht m als m^e mod n, waarbij n het product is van twee grote priemgetallen, en ontsleutelt met een tweede exponent d die alleen iemand die de twee priemgetallen kent, kan berekenen. In het schoolvoorbeeld zijn n = 3233 = 61 × 53, e = 17 en d = 413: 65 wordt 2790, en 2790 wordt weer 65.

Ontdek het zelf

Open de modulaire klok om a mod n, sommen, verschillen, producten, machten, inversen en quotiënten mod n te berekenen, voor getallen tot 30 cijfers. Elk antwoord komt met zijn stappen: de deling met rest, de machten uit herhaald kwadrateren of de tabel van het uitgebreide algoritme van Euclides. De klok tekent hoe het antwoord bereikt wordt, van de spiraal van een optelling tot de cyclus van machten, en voor kleine n toont de tabel van de bewerking alle antwoorden tegelijk.

Veelgestelde vragen

Wat betekent het symbool ≡?

a ≡ b (mod n) zegt dat a en b dezelfde rest geven bij deling door n, of, wat op hetzelfde neerkomt, dat n een deler is van a − b. 38 ≡ 2 (mod 12), omdat 38 − 2 = 36 een veelvoud van 12 is.

Is mod hetzelfde als de operator % bij het programmeren?

Voor positieve getallen wel. Voor negatieve getallen geven veel talen, zoals C, Java en JavaScript, een negatieve rest: −7 % 3 is daar −1, terwijl −7 mod 3 = 2. De % van Python volgt de wiskundige conventie voor een positieve n.

Wat is de orde van een getal mod n?

De kleinste k > 0 met a^k ≡ 1 (mod n). Die bestaat alleen als a en n geen gemeenschappelijke factor hebben. De orde van 2 mod 7 is 3, omdat 2³ = 8 ≡ 1, en de orde van 3 mod 7 is 6, dus de machten van 3 doorlopen elke rest behalve nul: 3 is een primitieve wortel mod 7.

Wie heeft modulair rekenen uitgevonden?

Resten werden al veel eerder gebruikt, bijvoorbeeld in de Chinese reststelling uit de 3e tot 5e eeuw, en door Fermat en Euler. Gauss maakte er in 1801 een systematische rekenkunde van, met de notatie van congruenties.

Klaar om het te proberen?

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

Open de modulaire klok