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. Als het 6 uur is, dan staat de klok 8 uur later niet op 14, maar op 14 − 12 = 2 uur.

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

In het bovenstaande voorbeeld van de klok zijn 6 + 8 en 2 congruent modulo 12, wat genoteerd wordt als:

$6+8\equiv 2{\pmod {12}}$

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

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:

0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, ...

en telt men 5 verder vanaf het getal 4, dan komt men bij 2 uit.

Wat is 4 × 5? Niet 20, maar 20 − 7 − 7 = 6. Dat kan ook zo gezien worden als

4 × 5 = 5 + 5 + 5 + 5 = (5 + 5) + 5 + 5 ≡ 3 + 5 + 5 = (3 + 5) + 5 ≡ 1 + 5 = 6

hierin geeft ≡ een equivalentierelatie aan

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

Met behulp van deze tabel kan men ook delingen uitvoeren. 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.

Definitie

Zij $n$ een natuurlijk getal ongelijk aan 0, dan heten de twee gehele getallen $a$ en $b$ congruent modulo $n$, genoteerd:

$a\equiv b{\bmod {n}}$,

als hun verschil $a-b$ een geheel veelvoud is van $n$.

Het getal $n$ wordt de modulus genoemd.

Opgemerkt moet worden dat de haakjes om ${\bmod {m}}$ ook wel worden weggelaten.

Het teken voor de modulus is in veel programmeertalen het procentteken %.

Toepassing

Het bekendste voorbeeld van modulair rekenen is de tijdrekening in hele uren (zie ook onder voor willekeurige tijden), die modulo 12 of modulo 24 gaat. Zo is de tijd bijvoorbeeld 10 uur na 22 uur gelijk aan 8 uur. Dus 10 + 22 = 8 modulo 24.

Geheeltallig rekenen in digitale computers vindt doorgaans plaats modulo $2^{n}$, waarbij $n$ het aantal bits is dat gebruikt wordt om een getal weer te geven. $n$ is dan begrensd door (meestal) de grootte van een processorregister. In een typische moderne computer heeft $n$ de waarde 32 of 64. Niet-modulair rekenen wordt door sommige programmeertalen ondersteund, maar gaat ten koste van de rekensnelheid.

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 0909337554 ≡ 93 (mod 97). Ook in de IBAN wordt een modulo 97 berekening uitgevoerd om een tweecijferig controlegetal te berekenen.

Algebra

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

In het bijzondere geval dat $m$ een priemgetal is, is $(\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 $p$ is relatief priem is met alle getallen $1,\ldots ,p-1$ Met behulp van het uitgebreide algoritme van Euclides kunnen voor elke $1\leq n<p$ getallen $x$ en $y$ gevonden worden, zodat $nx+py=\operatorname {ggd} (n,p)$.

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

• Als $a$ geen veelvoud is van $p$, geldt de implicatie

$a\cdot m\equiv a\cdot n{\bmod {p}}\Rightarrow m\equiv n{\bmod {p}}$

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

Machtsverheffen

Bij de machtsverheffing modulo $m$ mogen alleen de grondtallen herleid worden, niet de exponenten. Zo is bijvoorbeeld:

$8^{5}\equiv 3^{5}{\bmod {5}}$

$3^{5}\equiv 3{\bmod {5}}$

$3^{0}\equiv 1{\bmod {5}}$

Wel geldt de volgende stelling van Euler: als het grondtal geen delers gemeen heeft met $m$, dan mag de exponent worden herleid modulo de indicator $\varphi (m)$ van $m$.

Grote machten

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

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

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

Voorbeeld en tegenvoorbeeld bij de stelling van Euler

De Euler-indicator van 5 is 4, en inderdaad is:

$3^{5-4}\equiv 3{\bmod {5}}$

Dit geldt omdat 3 en 5 relatief priem zijn.

Daarentegen hebben 5 en 10 een deler gemeen en blijkt na herleiden van de exponent modulo 4, de Euler-indicator van 10, dat:

$5^{4}\equiv 5{\bmod {10}}{\mbox{ }},$ maar: $5^{0}\equiv 1{\bmod {10}}$

Reële getallen

Naar analogie van modulair rekenen met gehele getallen waarbij veelvouden van een bepaald geheel getal $a$ buiten beschouwing worden gelaten, kan men ook reële getallen optellen en aftrekken (en vermenigvuldigen met gehele getallen) waarbij veelvouden van een positief reëel getal $a$ buiten beschouwing worden gelaten. Een voorbeeld is het rekenen met de tijd van de dag, waarbij veelvouden van 24 uur buiten beschouwing worden gelaten, of de tijdweergave op een klok met wijzers, waarbij veelvouden van 12 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 $\mathbb {R} /a\mathbb {Z}$.

Als additieve groep kan vermenigvuldigen met gehele getallen worden toegevoegd omdat dit overeenkomt met herhaald optellen, of herhaald aftrekken van nul. Als men echter vermenigvuldigen van willekeurige elementen toevoegt (gedefinieerd door gewoon vermenigvuldigen, met het buiten beschouwing laten van veelvouden van $a$) wordt het geen ring, want bijvoorbeeld voor $b=\min(a/2,1)$ geldt $b\times (a/2+a/2)=b\times 0=0$, terwijl $b\times (a/2)+b\times (a/2)=ba$. Er geldt dus geen distributiviteit, het komt er op neer dat als een term $a$ buiten beschouwing wordt gelaten, dit uiteraard niet geldt voor een willekeurig reëel getal maal $a$.

Modulo-operator

Voor een niet-negatief geheel getal $a$ en een positief geheel getal $b$ is $a{\bmod {b}}$ een van de getallen 0, 1, .. $b-1$, zo dat $a-(a{\bmod {b}})$ een veelvoud van $b$ is.

Als $a$ en/of $b$ negatief is dan wordt soms een afwijkende definitie gehanteerd, waarbij $a{\bmod {b}}$ negatief kan zijn, maar wel nog steeds zo dat $a-(a{\bmod {b}})$ een veelvoud van $b$ is.

Bronnen, noten en/of referenties