Modulair rekenen

Modulair rekenen, of rekenen modulo een getal, is een vorm van geheeltallig rekenen met een getal dat als bovengrens fungeert, de modulus. Een typisch voorbeeld is de klok waarop modulo 12, of modulo 24, gerekend wordt. In het geval van modulo 12: als het bijvoorbeeld 6 uur is, dan staat de klok 8 uur later niet op 14, maar op 14 − 12 = 2 uur.

Bij modulair rekenen met modulus ${\displaystyle m}$ of rekenen modulo ${\displaystyle m}$ wordt gerekend met de getallen ${\displaystyle 0,1,\ldots ,m-1}$, waarna niet ${\displaystyle m}$ volgt maar weer opnieuw met 0 begonnen wordt. De ${\displaystyle m}$ getallen 0 tot en met ${\displaystyle m-1}$ staan als het ware in een kring. Het resultaat van een berekening modulo ${\displaystyle m}$ is de rest van het resultaat na geheeltallige deling door de modulus ${\displaystyle m}$. De normale definities van optellen en vermenigvuldigen worden gebruikt, maar als het resultaat groter is dan of gelijk aan ${\displaystyle m}$ wordt net zo vaak ${\displaystyle m}$ afgetrokken tot het resultaat weer kleiner is dan ${\displaystyle m}$. Getallen die modulo ${\displaystyle m}$ gelijk zijn, die dus een veelvoud van ${\displaystyle m}$ van elkaar verschillen, noemt men congruent modulo ${\displaystyle m}$, genoteerd met het symbool ${\displaystyle \equiv }$. Bijvoorbeeld

${\displaystyle 7\equiv 2{\pmod {5}}}$

De verzameling getallen waarmee modulo ${\displaystyle m}$ gerekend wordt, wordt aangeduid als ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$, naar het symbool ${\displaystyle \mathbb {Z} }$ dat de verzameling gehele getallen aanduidt.

Definities

Congruentie modulo m

Twee gehele getallen ${\displaystyle a}$ en ${\displaystyle b}$ heten congruent modulo het natuurlijke getal ${\displaystyle m>1}$, als hun verschil ${\displaystyle a-b}$ een geheel veelvoud is van ${\displaystyle m}$. Dit wordt genoteerd als:

${\displaystyle a\equiv b{\pmod {m}}}$.

Het getal ${\displaystyle m}$ wordt de modulus genoemd.

De haakjes in de uitdrukking geven aan dat ${\displaystyle {\bmod {m}}}$ van toepassing is op de hele vergelijking, en niet alleen op het rechterlid.

Equivalentierelatie

Congruentie modulo ${\displaystyle m}$ is een congruentierelatie, wat inhoudt dat het een equivalentierelatie is die compatibel is met het optellen en vermenigvuldigen van gehele getallen:

Als

${\displaystyle a_{1}\equiv a_{2}{\pmod {m}}\quad }$ en ${\displaystyle \quad b_{1}\equiv b_{2}{\pmod {m}}}$

dan

${\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {m}}\quad }$ en ${\displaystyle \quad a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {m}}}$

Modulo-operatie

De modulo-operatie is een binaire operatie ${\displaystyle a{\bmod {m}}}$ gedefinieerd voor natuurlijke getallen ${\displaystyle a}$ en een positief geheel getal ${\displaystyle m}$, zodanig dat ${\displaystyle a{\bmod {m}}}$ de rest is van de deling van ${\displaystyle a}$ door ${\displaystyle m}$, d.w.z. dat ${\displaystyle a{\bmod {m}}}$ een van de getallen ${\displaystyle 0,1,\ldots ,m-1}$ is waarvoor ${\displaystyle a-(a{\bmod {m}})}$ een veelvoud van ${\displaystyle m}$ is. Deze getallen ${\displaystyle 0,1,\ldots ,m-1}$ corresponderen met de equivalentieklassen van de congruentierelatie.

De definitie wordt wel uitgebreid voor het geval dat ${\displaystyle a}$ of ${\displaystyle m}$ negatief is. ${\displaystyle a{\bmod {m}}}$ kan dan negatief kan zijn, maar wel zo dat ${\displaystyle a-(a{\bmod {m}})}$ een veelvoud van ${\displaystyle m}$ is.

De operatie ${\displaystyle a{\bmod {m}}}$ wordt in de meeste programmeertalen met een % weergegeven, dus als a % m.^[1] In spreadsheets wordt daarvoor meestal een functie gebruikt zoals MOD(a,m)^[2] of REST(a;m).^[3]

Algebra

• ${\displaystyle a-(a{\bmod {m}})}$ is een veelvoud van ${\displaystyle m}$.
• ${\displaystyle a{\bmod {m}}\equiv a{\bmod {(}}-m)}$
• Als ${\displaystyle a}$ geen veelvoud is van ${\displaystyle p}$, geldt

${\displaystyle a\cdot x\equiv a\cdot y{\bmod {p}}\Leftrightarrow x\equiv y{\bmod {p}}}$

Bewijs 

Stel dat ${\displaystyle a{\bmod {p}}\not \equiv 0}$ en ${\displaystyle a\cdot x\equiv a\cdot y{\bmod {p}}}$.

${\displaystyle a\cdot x-a\cdot y\equiv 0{\bmod {p}}}$, dus ${\displaystyle a\cdot (x-y)\equiv 0{\bmod {p}}}$

${\displaystyle a{\bmod {p}}\not \equiv 0}$, dus is ${\displaystyle x-y\equiv 0{\bmod {p}}}$, dus is het verschil tussen ${\displaystyle x}$ en ${\displaystyle y}$ een veelvoud van ${\displaystyle p}$. ${\displaystyle x}$ is dus ${\displaystyle y}$ plus of min een veelvoud van ${\displaystyle p}$.

${\displaystyle x\equiv y{\bmod {p}}}$

Deze stelling wordt gebruikt bij het bewijs van de kleine stelling van Fermat.

Algemeen geldt: ${\displaystyle a\cdot x\equiv a\cdot y{\bmod {m}}\Rightarrow x\equiv y\operatorname {mod} \left({\frac {m}{\operatorname {ggd} (a,m)}}\right)}$

• ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$ is een ring en wel een commutatieve ring met een neutraal element. De elementen van ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ noemt men de restklassen modulo ${\displaystyle m}$.

In het bijzondere geval dat ${\displaystyle m}$ een priemgetal is, is ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$ zelfs een lichaam (Ned) / veld (Be).

Bewijs dat (Z/mZ) een lichaam is als m een priemgetal is 

Een priemgetal ${\displaystyle p}$ is relatief priem is met alle getallen ${\displaystyle 1,\ldots ,p-1}$ Met behulp van het uitgebreide algoritme van Euclides kunnen voor elke ${\displaystyle 1\leq n<p}$ getallen ${\displaystyle x}$ en ${\displaystyle y}$ gevonden worden, zodat ${\displaystyle nx+py=\operatorname {ggd} (n,p)}$.

Er geldt ${\displaystyle py\equiv 0{\bmod {p}}}$ en verder dat ${\displaystyle \operatorname {ggd} (n,p)=1}$. Voor elke ${\displaystyle n}$ is er dus een ${\displaystyle x}$ met ${\displaystyle nx=1\mod p}$.

Toepassing

Geheeltallig rekenen in digitale computers vindt doorgaans plaats modulo ${\displaystyle 2^{n}}$, waarbij ${\displaystyle n}$ het aantal bits is dat gebruikt wordt om een getal weer te geven. ${\displaystyle n}$ is dan begrensd door het datatype, vaak de grootte van een processorregister. ${\displaystyle n}$ heeft in een typisch modern computerprogramma de waarde 32 of 64. Niet-modulair rekenen wordt door sommige programmeertalen ondersteund, maar gaat ten koste van de rekensnelheid. Het teken voor de modulus is in veel programmeertalen het procentteken %.

Het Caesarcijfer, een vorm van encryptie, wordt op de manier van modulair rekenen geïmplementeerd.

In België heeft zowel een gestructureerde mededeling van een overschrijving, alsook het rekeningnummer en het rijksregisternummer als laatste twee cijfers een controlegetal dat modulo 97 congruent is met de voorgaande cijfers. Zo geldt bijvoorbeeld voor de gestructureerde mededeling +++090/9337/55493+++, dat aangeeft: 0909337554 ≡ 93 (mod 97). Ook in de IBAN wordt een modulo 97-berekening uitgevoerd om een tweecijferig controlegetal te berekenen.

Voorbeeld

Rekenen modulo 7 gebeurt met de getallen 0, 1, ..., 6. De uitkomst van 4 + 5 is niet 9, maar 9 − 7 = + 2. Denkt men de getallen in een kring of herhaald en telt men 5 verder vanaf het getal 4, dan komt men bij 2 uit.

Zo ook is 4 × 5 mod 7 = 6.

De onderstaande tabel geeft alle mogelijkheden voor de optelling modulo 7.

optelling modulo 7

+	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
6	6	0	1	2	3	4	5

Voor de vermenigvuldiging kan ook een tabel worden gemaakt.

vermenigvuldiging modulo 7

×	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
6	0	6	5	4	3	2	1

Omdat 7 een priemgetal is kan men met behulp van deze tabel ook delingen uitvoeren (zie ook onder). Wat is 5 : 4 modulo 7? Noem dit getal q, dan is 4 q ≡ 5 modulo 7. Uit de tabel kan men aflezen dat q = 3, dus 5 : 4 ≡ 3 modulo 7.

Machtsverheffen

Bij machtsverheffen modulo ${\displaystyle m}$ mogen de grondtallen worden herleid. Zo is bijvoorbeeld:

${\displaystyle 8^{5}\equiv 3^{5}{\bmod {5}}}$, omdat ${\displaystyle 8\equiv 3{\bmod {5}}}$,

${\displaystyle 3^{5}\equiv 3{\bmod {5}}}$, een voorbeeld van de kleine stelling van Fermat en

${\displaystyle 3^{0}\equiv 1{\bmod {5}}}$, evident.

De stelling van Euler geeft aan wanneer een macht ook naar de exponent kan worden herleid. Als het grondtal van de macht en ${\displaystyle m}$ relatief priem zijn, dan mag de exponent worden herleid modulo de indicator ${\displaystyle \varphi (m)}$ van ${\displaystyle m}$.

Grote machten

Machtsverheffen modulo ${\displaystyle m}$ tot grote machten kan relatief gemakkelijk uitgevoerd worden met behulp van machtsverheffing door kwadrateren, aangezien

${\displaystyle (x{\bmod {m}})^{2}\equiv x^{2}{\bmod {m}}}$

Om ${\displaystyle 298^{187}{\bmod {3}}19}$ uit te rekenen kunnen achtereenvolgens de machten ${\displaystyle 298^{2}{\bmod {3}}19}$, ${\displaystyle (298^{2})^{2}{\bmod {3}}19}$, ${\displaystyle (298^{4})^{2}{\bmod {3}}19,\ldots ,298^{128}{\bmod {3}}19}$ berekend worden. Omdat ${\displaystyle 187=128+32+16+8+2+1}$, wordt de gevraagde macht bepaald als het product modulo 319 van de overeenkomstige machten.

Reële getallen

Het komt in meer situaties voor, dat veelvouden van een bepaald geheel getal ${\displaystyle a}$ buiten beschouwing worden gelaten, zoals dat bij modulair rekenen gebeurt. Een voorbeeld is het rekenen met de tijd van de dag, waarbij veelvouden van 24 uur buiten beschouwing worden gelaten en daarmee corresponderend, rekenen met hoeken, waarbij volledige omwentelingen buiten beschouwing worden gelaten. De groep met betrekking tot de optelling is de cirkelgroep ${\displaystyle \mathbb {R} /a\mathbb {Z} }$.

Bij de grootheid tijd wordt modulo een dag gerekend.^[4] Zo kan men een tijdsduur optellen bij een tijd van de dag, 3 uur en 20 minuten na het tijdstip 23:15 is het bijvoorbeeld 2:35. Om bij een halfuurdienst van een trein te bepalen hoe lang men moet wachten gaat het om de vertrektijd van de trein modulo een half uur en de kloktijd waarop men op het station is, modulo een half uur.