Modulair rekenen intuïtief begrijpen (Klokrekenen en waarom de rest de baas is)

Het is negen uur en er vertrekt over vijf uur een vlucht. Niemand antwoordt "veertien uur." Je zegt twee, en je deed het zonder nadenken, want een wijzerplaat heeft geen veertien. De uren lopen bij twaalf rond en beginnen opnieuw. Je doet al aan modulair rekenen sinds je klok kunt kijken; je hebt de notatie alleen nog nooit ontmoet.

Dat is het hele onderwerp. Kies een getal om bij rond te lopen, vergeet elke volle ronde, en bewaar alleen waar je landt. Wat dit een artikel waard maakt, is dat die ene gewoonte, alleen de rest bewaren, problemen oplost die frontaal onmogelijk lijken: het laatste cijfer van een getal met zeventig cijfers, of een reusachtig getal deelbaar is door 9, waarom een creditcardnummer geldig is of niet, en hoe een bericht zo door de war gehaald kan worden dat alleen de bedoelde lezer het kan ontwarren.

Dit artikel is het beeld: wat een rest werkelijk is, waarom je mag vereenvoudigen vóór je rekent, wat er gebeurt met negatieve getallen en met machten, en waar de enige echte moeilijkheid, het delen, vandaan komt.

Een rest is waar je landt, niet wat er over is

De standaarddefinitie zegt dat $a \bmod n$ de rest is wanneer $a$ door $n$ wordt gedeeld. Dat is correct en het is ook de reden dat het onderwerp als een karweitje voelt, want "rest" klinkt als het restafval na een deling, een bijkomstigheid.

Een beter beeld: een ronde baan met $n$ markeringen erop, genummerd $0$ tot $n-1$. Om $a \bmod n$ te vinden, start je bij $0$ en loop je $a$ stappen over de baan. Waar je stopt, is het antwoord. Met 17 stappen over een baan met 5 markeringen ga je drie volle ronden (15 stappen) en dan nog 2, dus je stopt bij markering 2. Vandaar $17 \bmod 5 = 2$. De volle ronden zijn het quotiënt; waar je landt is de rest.

Dit beeld doet twee dingen die de definitie niet doet. Het zorgt ervoor dat de rest altijd tussen $0$ en $n-1$ landt, want dat zijn de enige markeringen. En het verklaart waarom twee getallen mod $n$ "hetzelfde" kunnen zijn terwijl ze hemelsbreed verschillen: $2$, $17$, $102$ en $5{,}000{,}002$ stoppen allemaal bij markering 2 op een baan met 5 markeringen. Ze verschillen in ronden, en de baan houdt geen ronden bij.

Wiskundigen schrijven dat idee als een congruentie:

$$17 \equiv 2 \pmod{5}$$

Lees het als "17 landt waar 2 landt, op de 5-baan." De drievoudige streep is geen isgelijkteken, want 17 en 2 zijn niet gelijk. Hij zegt dat ze onderling verwisselbaar zijn voor elke vraag die alleen om de positie op de baan geeft. De precieze versie: $a \equiv b \pmod{n}$ betekent dat $n$ de waarde $a - b$ deelt, wat niets anders zegt dan dat de twee getallen een heel aantal ronden verschillen.

Optellen en vermenigvuldigen geven alleen om waar je staat

Hier is het feit dat modulair rekenen tot gereedschap maakt in plaats van een curiositeit. Ga je twee getallen optellen en daarna de rest bepalen, dan mag je eerst de resten bepalen, die optellen en opnieuw vereenvoudigen. Het antwoord is identiek. Hetzelfde geldt voor aftrekken en vermenigvuldigen.

Op de baan is het duidelijk. 17 optellen betekent 17 stappen lopen, en dat is drie ronden plus 2. De drie ronden brengen je terug waar je begon en veranderen niets, dus 17 optellen heeft precies hetzelfde effect als 2 optellen. De ronden die in een getal verstopt zitten zijn dood gewicht, en ze blijven dood gewicht door het optellen en door het vermenigvuldigen heen, want een veelvoud van $n$ maal wat dan ook is nog steeds een veelvoud van $n$.

Uitgeschreven, met $a = qn + r$ en $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Alles in het eerste haakje is ronden. Alleen $rs$ overleeft, dus $ab \bmod n$ is $rs \bmod n$. De resten dragen alle informatie die de vraag nodig heeft.

Daarom zegt de tip in het rekenonderwerp van Math Zen dat je stap voor stap moet vereenvoudigen in plaats van de volle waarde uit te rekenen. Stel dat je $123 \times 456 \bmod 7$ wilt. Je kunt uitvermenigvuldigen tot 56.088 en een staartdeling door 7 doen. Of je merkt op dat $123 = 119 + 4$, dus $123 \equiv 4$, en $456 = 455 + 1$, dus $456 \equiv 1$, en het antwoord is $4 \times 1 = 4$. Twee kleine vereenvoudigingen vervangen een vermenigvuldiging met viercijferige getallen. De gewoonte is: laat een getal nooit boven $n$ uit groeien als je alleen om de rest geeft.

Negatieve getallen lopen de andere kant op

Het baanbeeld behandelt ook het geval waar de meeste mensen over struikelen. Wat is $-3 \bmod 5$?

Loop 3 stappen achteruit vanaf 0 op een baan met 5 markeringen. Je passeert 4, dan 3, en landt op 2. Dus $-3 \equiv 2 \pmod{5}$. Een negatief getal is gewoon een wandeling de andere kant op, hetzelfde idee als in Negatieve getallen intuïtief begrijpen, en de rest is nog steeds waar je landt, nog steeds tussen $0$ en $n-1$.

De snelle weg: tel ronden op tot het getal positief is. $-3 + 5 = 2$. Voor $-14 \bmod 5$ tel je 15 op (drie ronden) en krijg je 1. Rekenmachines en programmeertalen zijn onderling oneens over negatieve resten, sommige geven $-4$ voor $-14 \bmod 5$, dus geef op een toets het antwoord altijd als de niet-negatieve markering op de baan, en controleer de afspraak van je rekenmachine voordat je erop vertrouwt.

Met aftrekken is het hetzelfde verhaal. $3 - 8 \pmod{5}$ is $-5$, precies één ronde achteruit, dus het antwoord is 0. Of vereenvoudig eerst: $8 \equiv 3$, dus $3 - 3 = 0$.

Het laatste cijfer van een reusachtige macht

Dit is het probleem dat mensen ervan overtuigt dat het onderwerp het kennen waard is, en het is een direct gevolg van de regel om eerst te vereenvoudigen.

Het laatste cijfer van een getal is het getal mod 10, want de tientallen, honderdtallen en alles daarboven zijn veelvouden van 10 en landen terug op 0 op een baan met 10 markeringen. Dus "wat is het laatste cijfer van $7^{100}$" is de vraag "wat is $7^{100} \bmod 10$," en je hoeft $7^{100}$ nooit uit te rekenen.

Kijk in plaats daarvan hoe de machten van 7 over de 10-baan lopen, terwijl je elke keer vereenvoudigt:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

Zodra je bij 1 komt, begint de cyclus opnieuw: 7, 9, 3, 1, 7, 9, 3, 1, met periode 4. Omdat $100 = 4 \times 25$, zit de honderdste macht aan het eind van een volledige cyclus, op dezelfde plek als $7^4$, en is het laatste cijfer 1.

Elk grondtal heeft een cyclus mod 10, en de meeste zijn kort. Machten van 2 lopen door 2, 4, 8, 6. Machten van 3 door 3, 9, 7, 1. Machten van 5 en 6 bewegen nooit. De methode is altijd dezelfde: vind de cycluslengte door te vereenvoudigen terwijl je gaat, deel de exponent door de cycluslengte, en de rest van die deling vertelt je waar in de cyclus je zit. Het is het idee van exponenten als herhaald vermenigvuldigen, uitgevoerd op een ronde baan in plaats van op een rechte lijn.

Waarom de cijfersomtest voor 9 werkt

Iedereen leert dat een getal deelbaar is door 9 als zijn cijfers optellen tot een negenvoud, en bijna niemand leert waarom. Modulair rekenen maakt er een argument van één regel van.

Tien is één ronde plus één op een 9-baan: $10 \equiv 1 \pmod{9}$. Dan is $100 = 10 \times 10 \equiv 1 \times 1 = 1$, en elke macht van 10 is eveneens congruent met 1. Dus een getal als $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ is congruent met $4 + 5 + 2 + 7 = 18 \pmod{9}$, en 18 is $0$ op de 9-baan, dus 4.527 is deelbaar door 9. De cijfersom is geen truc. Het is het getal zelf, gezien mod 9.

De test voor 3 werkt om dezelfde reden, want ook $10 \equiv 1 \pmod{3}$. De test voor 11 komt van $10 \equiv -1 \pmod{11}$, waardoor de machten van 10 afwisselen tussen $1$ en $-1$ en je de alternerende cijfersom krijgt. Al die deelbaarheidsregels die je uit je hoofd moest leren, zijn één feit, "vereenvoudig de machten van 10," toegepast op verschillende banen.

Controlecijfers: modulair rekenen in je portemonnee

Elk ISBN, elk creditcardnummer en elke streepjescode eindigt met een cijfer dat als enige taak heeft om een rest te zijn.

Het laatste cijfer van een ISBN met 13 cijfers is zo gekozen dat een gewogen som van alle dertien cijfers, met gewichten die afwisselen tussen 1 en 3, congruent is met $0 \pmod{10}$. Typ één cijfer verkeerd en de som landt elders op de 10-baan, waarna de scanner hem afwijst. Creditcards gebruiken het Luhn-algoritme, een iets slimmere weging die ook de meeste gevallen opvangt waarin twee naast elkaar liggende cijfers verwisseld zijn, alweer door een som mod 10 te controleren.

Dit zijn de bescheiden neefjes van een veel grotere toepassing. Moderne versleuteling rust op het feit dat een getal tot een macht verheffen mod een heel grote $n$ eenvoudig is, terwijl het proces omkeren zonder geheime sleutel dat niet is. Het zoeken van de cyclus dat je hierboven deed voor $7^{100}$ is dezelfde bewerking, opgeschaald naar getallen met honderden cijfers, en de regel om onderweg te vereenvoudigen is de enige reden dat het überhaupt te berekenen valt.

Delen is waar de baan hobbelig wordt

Optellen, aftrekken en vermenigvuldigen gedragen zich op een baan precies zoals op de getallenlijn. Delen niet, en dat is de ene plek waar het onderwerp zijn reputatie verdient.

Op de gewone getallenlijn betekent delen door 4 vermenigvuldigen met $\tfrac{1}{4}$, het getal dat maal 4 gelijk is aan 1. Is er op een 12-baan een markering die maal 4 op 1 landt? Probeer ze allemaal: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, en het patroon 4, 8, 0 herhaalt zich eeuwig. Het raakt nooit 1. Dus op de 12-baan bestaat delen door 4 niet.

De reden is dat 4 en 12 een factor delen. Begin met een viervoud, tel ronden van 12 op of haal ze eraf, en je hebt nog steeds een viervoud, dus je kunt nooit 1 voorbij een twaalfvoud landen. Probeer 5 eens: $5 \times 5 = 25 = 24 + 1 \equiv 1$, dus 5 is zijn eigen inverse op de 12-baan en delen door 5 kan prima. De regel: $a$ heeft een inverse mod $n$ precies wanneer $a$ en $n$ geen gemeenschappelijke factor behalve 1 delen.

Die regel heeft een opvallend gevolg. Is $n$ een priemgetal, dan deelt niets van $1$ tot $n - 1$ een factor met hem, dus heeft elke markering behalve nul een inverse en kun je vrij delen. Priembanen zijn de banen waar alle vier de bewerkingen werken, en dat is een groot deel van de reden dat priemgetallen, waarvan de oneindige voorraad gegarandeerd is, in het hart van de getaltheorie en van de cryptografie zitten.

Waar de fouten vandaan komen

Modulair rekenen heeft weinig bewegende delen, en de fouten zijn dan ook heel specifiek.

De eerste is het vereenvoudigen van de exponent in plaats van het grondtal. In $7^{100} \bmod 10$ mag je 7 mod 10 vereenvoudigen (dat is hij al), en mag je de exponent mod de cycluslengte vereenvoudigen zodra je die kent, maar je mag niet 100 mod 10 nemen en $7^0$ uitrekenen. Exponenten leven op een andere baan, de baan waarvan de omvang de cycluslengte is, en die twee banen door elkaar halen is de meest voorkomende fout bij dit onderwerp.

De tweede is een negatieve rest. $-14 \bmod 5$ is 1, niet $-4$. Dezelfde positie op de baan, maar slechts één van de twee is de afgesproken naam, en antwoordmodellen willen de niet-negatieve.

De derde is delen zonder te controleren of er een inverse bestaat. Een gemeenschappelijke factor aan weerszijden van een congruentie wegstrepen mag alleen als die factor niets met de modulus deelt. Uit $4 \times 2 \equiv 4 \times 5 \pmod{12}$, wat waar is omdat beide kanten 8 zijn, mag je de 4 niet wegstrepen om te concluderen dat $2 \equiv 5$, wat onwaar is. De ronden die je bij het wegstrepen weggooit, moeten ronden van de oorspronkelijke baan zijn.

De vierde is vergeten aan het eind te vereenvoudigen. Als je $rs = 21$ krijgt op een 7-baan en 21 opschrijft, is dat niet precies fout, maar het is ook geen antwoord. Het antwoord is een markering op de baan, en 21 is drie ronden, dus de markering is 0.

Waar Math Zen van pas komt

Het rekenonderwerp van Math Zen heeft een eigen bak voor modulair rekenen, en de opbouw is gebouwd rond de gewoonte om eerst te vereenvoudigen in plaats van rond de notatie. Vroege opgaven vragen gewone resten en congruenties met kleine moduli, tot "waar land ik" automatisch gaat. De middelste bakken mengen negatieve getallen en producten erin, waar het punt is om elke factor te vereenvoudigen vóór het vermenigvuldigen en de niet-negatieve rest te noemen. De latere bakken zijn de opgaven over laatste cijfers en cycluslengtes, precies die op wedstrijdopgaven en toelatingstoetsen opduiken en die iedereen afstraffen die de volle macht probeert uit te rekenen.

Omdat de sessies kort zijn en de opgaven met tussenpozen terugkomen, zoals beschreven in gespreide herhaling voor wiskundeoefening, wordt het zoeken van de cyclus een reflex in plaats van een procedure die je opzoekt. De meeste mensen hebben geen hiaat in modulair rekenen dat een hoofdstuk zou dichten. Ze hebben één beeld, de baan, dat nooit voor hen getekend is, en ongeveer veertig herhalingen die nooit gedaan zijn.

De conclusie

Modulair rekenen is rekenen op een ronde baan met $n$ markeringen. Een rest is waar je landt na $a$ stappen, volle ronden worden vergeten, en twee getallen zijn congruent wanneer ze op dezelfde markering landen. Omdat ronden niets bijdragen aan sommen en producten, mag je elk getal tot zijn rest vereenvoudigen vóór je optelt of vermenigvuldigt, en die ene toestemming verandert onmogelijke berekeningen, zoals het laatste cijfer van $7^{100}$, in korte cycli die je met de hand kunt natrekken. Deelbaarheidstesten zijn de machten van 10 vereenvoudigd mod 9, 3 of 11. Controlecijfers zijn resten die typefouten opvangen. Delen werkt alleen wanneer het getal geen factor met de baan deelt, en daarom zijn priembanen bijzonder.

Loopt een modulair probleem vast, teken dan de baan. Vraag waar elk stuk landt, vereenvoudig onderweg, en houd de exponent op zijn eigen baan. Het antwoord is een markering tussen $0$ en $n - 1$, en het beeld brengt je er eerder dan de formule.