Wat betekent het teken $\equiv$?

Je leest het als ‘is congruent met’. $17 \equiv 5 \pmod{12}$ zegt dat 17 en 5 bij deling door 12 dezelfde rest geven (allebei 5). Het is zwakker dan $=$: congruente getallen kunnen verschillende getallen zijn die op dezelfde plek van de wijzerplaat uitkomen.

Waarom mag ik de getallen eerst herleiden?

Schrijf $a = pn + r$ en $b = qn + s$. Dan is $a + b = (p + q)n + (r + s)$ en $a \times b = (pqn + ps + qr)n + rs$. De delen met $n$ zijn veelvouden van $n$ en laten geen rest over, dus alleen $r + s$ en $r \times s$ bepalen de uitkomst.

Waar wordt modulair rekenen buiten school gebruikt?

Bij controlecijfers (streepjescodes, ISBN, de IBAN van een bankrekening, die modulo 97 gecontroleerd wordt), in de informatica (hashtabellen, generatoren van willekeurige getallen) en in de cryptografie: de RSA-methode die internetbankieren beveiligt, rekent met enorme getallen modulo een product van twee priemgetallen.

Leermiddelen

Modulair rekenen

Leer klokrekenen: resten, a mod n, congruentie modulo n en hoe je ze gebruikt voor weekdagen, controlecijfers en het laatste cijfer van enorme machten.

Gevorderd25 minLes

Delen in Classroom

Werkblad om te printen

Definitie

Modulair rekenen is rekenen met resten. Je kiest een vast geheel getal

n \geq 2

, de modulus, en van een getal houd je alleen de rest bij deling door

n

a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1

Bijvoorbeeld

17 \bmod 5 = 2

, want

17 = 3 \times 5 + 2

Twee getallen zijn congruent modulo n als ze dezelfde rest geven. Dat is hetzelfde als zeggen dat

n

een deler is van hun verschil:

a \equiv b \pmod{n} \iff n \text{ deelt } a - b

Dus

38 \equiv 14 \pmod{12}

, want

38 - 14 = 24 = 2 \times 12

(allebei rest

2

Een klok werkt precies zo: na 12 uur staat de wijzer weer op dezelfde plek, dus 15 uur en 3 uur zijn dezelfde plek,

15 \equiv 3 \pmod{12}

. In sommen, verschillen en producten mag je elk getal eerst door zijn rest vervangen en de uitkomst aan het eind nog een keer herleiden.

Probeer het meteen

Wat is

23 \bmod 5

Uitgewerkte voorbeelden

Bereken

47 \bmod 6

Zoek het grootste veelvoud van 6 dat niet groter is dan 47

6 \times 7 = 42

, terwijl

6 \times 8 = 48

al te groot is →

42

Schrijf 47 als quotiënt keer 6 plus rest

47 = 7 \times 6 + 5

→ rest

5

Controleer dat de rest tussen 0 en 5 ligt

0 \leq 5 \leq 5

, dus het is een geldige rest →

47 \bmod 6 = 5

Antwoord: $47 \bmod 6 = 5$ , dus $47 \equiv 5 \pmod{6}$ . Het quotiënt $7$ hoort niet bij het antwoord.

Veelgemaakte fouten

$-3 \bmod 12 = -3$ (of $3$ ) schrijven

Waarom het fout is: Een rest moet een van de getallen $0, 1, \ldots, n - 1$ zijn. Als je vanaf 12 uur 3 uur teruggaat, kom je niet op een negatief getal uit en ook niet op 3.

Correct: Tel de modulus erbij op tot het getal in het bereik ligt: $-3 + 12 = 9$ , dus $-3 \bmod 12 = 9$ .

Zeggen dat 9 uur plus 4 uur op een 12-uursklok 13 uur is

Waarom het fout is: De som $9 + 4 = 13$ klopt, maar de laatste herleiding ontbreekt. Elke uitkomst moet nog een keer herleid worden.

Correct: $13 \bmod 12 = 1$ : de klok wijst 1 aan.

Het quotiënt geven in plaats van de rest: $47 \bmod 6 = 7$

Waarom het fout is: $47 : 6 = 7$ rest $5$ . De bewerking mod houdt alleen bij wat overblijft, niet hoe vaak 6 in 47 past.

Correct: $47 \bmod 6 = 5$ , want $47 = 7 \times 6 + 5$ .

De exponent herleiden met de modulus: $2^9 \bmod 7$ wordt $2^2 = 4$ omdat $9 \bmod 7 = 2$

Waarom het fout is: Het grondtal mag je modulo $n$ herleiden, de exponent niet. De exponent volgt de lengte van de cyclus van machten, en die is hier 3, niet 7.

Correct: Machten van 2 modulo 7 zijn $2, 4, 1, 2, 4, 1, \ldots$ (cycluslengte 3). $9 \bmod 3 = 0$ , dus $2^9 \equiv 1 \pmod{7}$ . Controle: $512 = 73 \times 7 + 1$ .

Interactieve visualisatie

9 uur plus 100 uur: tel de rondes

12 plekken op de wijzerplaat: modulo 12

Start

Optellen

Begin bij 9 en ga 100 uur vooruit.

Weekdagen rekenen modulo 7: eerst gokken, dan kijken

7 plekken op de wijzerplaat: modulo 7

Waar komt de wijzer uit? Tik op de plek op de wijzerplaat.

2 + 100 ≡ ? (mod 7)

Begin bij wo en ga 100 dagen vooruit.

Congruent modulo 12: dezelfde plek op de wijzerplaat

12 plekken op de wijzerplaat: modulo 12

Eerste getal

Tweede getal

38 = 3 × 12 + 2

14 = 1 × 12 + 2

38 − 14 = 24 = 2 × 12

38 ≡ 14 (mod 12)

38 en 14 komen op dezelfde plek uit, want hun verschil 24 is een veelvoud van 12.

Getallen op de plek 2: … -10, 2, 14, 26, 38 …

De laatste cijfers van machten van 3 (modulo 10) herhalen zich

10 plekken op de wijzerplaat: modulo 10

Grondtal

Exponent

Vermenigvuldig steeds weer met 3 en houd telkens alleen de rest.

Interactieve sandbox

Expressiecalculator

Probeer deze:

Geschiedenis

Nog geen berekeningen

Oefenproblemen

18 opgaven

Opgave 1 van 18

Makkelijk

Wat is

23 \bmod 5

Waarom het belangrijk is

Modulair rekenen is de wiskunde van alles wat rondgaat:

Tijd: klokken tellen modulo 12 of 24, weekdagen modulo 7. Hoe laat is het over 100 uur? Welke dag is het over 100 dagen?
Controlecijfers: het laatste cijfer van een streepjescode (EAN-13) wordt modulo 10 gekozen, dat van een ISBN-10 modulo 11, en de IBAN van een bankrekening wordt gecontroleerd modulo 97. Eén verkeerd getypt cijfer en de controle mislukt.
Enorme getallen: je kunt het laatste cijfer van $3^{100}$ (een getal van 48 cijfers) uit je hoofd vinden, want laatste cijfers zijn resten modulo 10 en die herhalen zich in een cyclus.
Informatica: hashtabellen, generatoren van willekeurige getallen en de RSA-versleuteling achter internetbankieren rekenen allemaal modulo $n$ .

Eén geval ken je al: even en oneven is gewoon rekenen modulo 2 (rest 0 of 1).

Toepassingen in de echte wereld

Kalenders: welke dag wordt het?

Een week heeft 7 dagen, dus de weekdagen herhalen zich modulo 7. Agenda-apps, dienstregelingen en verjaardagspuzzels gebruiken dat voortdurend.

Voorbeeld:

Een gewoon jaar heeft $365$ dagen en $365 = 52 \times 7 + 1$ . Een verjaardag die dit jaar op maandag valt, valt volgend jaar dus op dinsdag (tenzij er een 29 februari tussen zit).

1Probeer het zelf

Vandaag is het woensdag. Je uitwisseling begint over precies 100 dagen. Nummer de dagen maandag $= 0$ , dinsdag $= 1$ enzovoort tot zondag $= 6$ .

Op welke dag van de week begint de uitwisseling?

Stap 1: Kies het juiste antwoord

Kies de dag:

Streepjescodes en controlecijfers

Het laatste cijfer van elke EAN-13-streepjescode is een controlecijfer, gekozen met rekenen modulo 10. De scanner rekent het opnieuw uit en weigert een code met een verkeerd gelezen cijfer.

Voorbeeld:

Voor de boekcode $978030640615$ is de gewogen som (gewichten $1, 3, 1, 3, \ldots$ ) gelijk aan $93$ , en $93 \bmod 10 = 3$ . Het controlecijfer is $10 - 3 = 7$ , dus de volledige code is $9780306406157$ .

2Probeer het zelf

Een winkel maakt een productcode met de 12 cijfers $400123456789$ . De cijfers op de posities 1, 3, 5, ... tellen één keer, de cijfers op de posities 2, 4, 6, ... tellen drie keer. Het controlecijfer maakt het totaal een veelvoud van 10.

Wat is het controlecijfer?

Stap 1: Schrijf de wiskundige uitdrukking

Controlecijfer:

Ploegendienst en de 24-uursklok

Dienstregelingen van treinen, diensten in het ziekenhuis en vluchtschema's gebruiken de 24-uursklok, en dat is rekenen modulo 24.

Voorbeeld:

Een nachtdienst begint om 22:00 uur en duurt 9 uur: $22 + 9 = 31$ en $31 \bmod 24 = 7$ , dus hij eindigt om 07:00 uur.

3Probeer het zelf

Een machinetest in een fabriek begint om 19:00 uur en loopt 75 uur zonder pauze.

Op welk uur (0 tot en met 23) eindigt de test?

Stap 1: Schrijf de wiskundige uitdrukking

Einduur:

Belangrijke punten

1 $a \bmod n$ is de rest van $a : n$ en is altijd een van de getallen $0, 1, \ldots, n - 1$
2 $a \equiv b \pmod{n}$ betekent dat $a$ en $b$ dezelfde rest geven, en dat is hetzelfde als: $n$ deelt $a - b$
3Een klok rekent modulo 12, de 24-uursklok modulo 24, de weekdagen modulo 7 en even/oneven modulo 2
4In sommen, verschillen en producten mag je elk getal eerst herleiden en daarna de uitkomst nog een keer
5Bij een negatief getal tel je $n$ erbij op tot het in $0, \ldots, n - 1$ valt: $-3 \bmod 12 = 9$
6Machten herhalen zich modulo $n$ in cycli: bepaal de cycluslengte en herleid de exponent modulo die lengte, niet modulo $n$

Veelgestelde vragen

Voor positieve getallen wel. Voor negatieve getallen geven veel programmeertalen een negatieve uitkomst, bijvoorbeeld

-3

voor

-3

gedeeld door

12

. In de wiskunde ligt de rest altijd tussen

0

n - 1

, dus

-3 \bmod 12 = 9

. De rekenmachine op deze pagina werkt zo: mod(-3, 12) geeft 9.

Woordenlijst

Modulus: Het vaste getal $n$ waardoor je deelt; de resten zijn $0, 1, \ldots, n - 1$ (12 bij een klok, 7 bij de weekdagen)
Rest: Wat er bij het delen overblijft: in $a = q \times n + r$ met $0 \leq r \leq n - 1$ is dat $r$
a mod n: De rest van $a$ bij deling door $n$ , bijvoorbeeld $17 \bmod 5 = 2$ en $-3 \bmod 12 = 9$
Congruent modulo n: Twee getallen met dezelfde rest modulo $n$ , genoteerd als $a \equiv b \pmod{n}$ ; gelijkwaardig: $n$ deelt $a - b$
Cycluslengte: Na hoeveel stappen de resten van machten zich gaan herhalen, bijvoorbeeld 4 voor de laatste cijfers van machten van 3
Controlecijfer: Een extra cijfer aan het eind van een code (streepjescode, ISBN), zo gekozen dat een gewogen som deelbaar is door 10 of 11

Formulekaart

Deling met rest

a = q \times n + r, \quad 0 \leq r \leq n - 1

$r$ is $a \bmod n$, $q$ is het quotiënt

Congruentie

a \equiv b \pmod{n} \iff n \mid (a - b)

Dezelfde rest, of: het verschil is een veelvoud van $n$

Eerst herleiden

(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n

Hetzelfde geldt voor aftrekken en vermenigvuldigen

Negatieve getallen

x \bmod n = (x + k \times n) \bmod n

Tel een veelvoud van $n$ op tot het getal in $0, \ldots, n - 1$ valt: $-3 + 12 = 9$

Uitdaging van vandaagEén opgave, drie pogingen

Meer over dit onderwerp

Even en oneven getallen

Basis15 min

Kwadraten en kwadraatgetallen

Gemiddeld25 min