Modulorekenen | Wiskunde is leuk

De eindige rekenkunde, ook wel modulaire rekenkunde genoemd, wordt beschreven in het boek Disquisitiones Arithmeticae van Gauss, een buitengewoon invloedrijk werk uit 1801, toen de auteur nog maar vierentwintig jaar oud was.

Stel $a,b,m \in \mathbb{Z},m>1$ . Indien $a$ en $b$ bij deling door $m$ dezelfde rest geven, d.w.z. indien $a-b=cm$ voor zekere $c \in \mathbb{Z}$ , heten $a$ en $b$ congruent modulo $m$ . We noteren $a\equiv b$ mod m.Zo is bijvoorbeeld $3\equiv 63$ mod 5, $7\equiv -1$ mod 8 en $12^2\equiv 1$ mod 13.

Enkele eigenschappen :

Als $a\equiv b$ mod m en $b\equiv c$ mod m, dan is $a\equiv c$ mod m.
Als $a\equiv b$ mod m en $c\equiv d$ mod m, dan is $a+c\equiv b+d$ mod m.
Als $a\equiv b$ mod m en $n \in \mathbb{N}$ , dan is $a^n\equiv b^n$ mod m.
Als $a\equiv b$ mod m dan is voor elke $c \in \mathbb{Z}$ : $ac\equiv bc$ mod m.
Als $a\equiv b$ mod m en $c\equiv d$ mod m, dan is $ac\equiv bd$ mod m.

Rekenen met congruenties lijkt erg op het rekenen met vergelijkingen. Er is echter een belangrijk verschil: uit $ac\equiv bc$ mod m met $c\neq 0$ mod m hoeft niet te volgen dat $a\equiv b$ mod m. Zo is $6.12\equiv 6.7$ mod 10 maar 12 is niet congruent met 7 modulo 10. In andere gevallen gaat het wel op. De voorwaarde waarop de vereenvoudiging met $c$ wel kan, is dat $c$ onderling ondeelbaar is met $m$ .
Dus als $ac\equiv bc$ mod m en ggd(c,m) = 1, dan is $a\equiv b$ mod m.
Als ggd(c,m) = d, dan volgt uit $ac\equiv bc$ mod m dat $a\equiv b$ mod( $\frac{m}{d}$ ).

Rekent men modulo $m$ , dan zijn er $m$ verschillende soorten getallen, al naar gelang ze verschillende resten geven bij deling door $m$ . De verzameling van alle gehele getallen die eenzelfde rest geven heet een restklasse modulo $m$ . Er zijn dus precies $m$ verschillende restklassen modulo $m$ . De restklasse die een getal $a$ bevat, noteert men als $\overline{a}$ . Deze notatie is natuurlijk niet eenduidig bepaald, want als $a\equiv b$ mod m, stellen $\overline{a}$ en $\overline{b}$ dezelfde restklasse modulo $m$ voor en omgekeerd.

Werken we modulo 4 dan is $\overline{0}=\left\{0,4,8,12,\cdots}\right\}$ , $\overline{1}=\left\{1,5,9,13,\cdots\right\}$ , $\overline{2}=\left\{2,6,10,14,\cdots\right\}$ , $\overline{3}=\left\{3,7,11,15,\cdots\right\}$ .

Men kan in de verzameling restklassen modulo $m$ , genoteerd door $\mathbb{Z}_m$ , een optelling en een vermenigvuldiging defini\”eren via $\overline{a}+\overline{b}=\overline{a+b}$ en $\overline{a}.\overline{b}=\overline{ab}$ . Deze rekenregels lijken erg op de regels van optelling en vermenigvuldiging van gehele getallen.

Eigenschappen :

$\forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}+\overline{b}=\overline{b}+\overline{a}.$
$\forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}.\overline{b}=\overline{b}.\overline{a}.$
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}+\overline{b})+\overline{c}=\overline{a}+(\overline{b}+\overline{c})$ .
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}.\overline{b}).\overline{c}=\overline{a}.(\overline{b}.\overline{c})$ .
$\forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : \overline{a}.(\overline{b}+\overline{c})=\overline{a}.\overline{b}+\overline{a}.\overline{c}$ .
$\forall \overline{a}\in \mathbb{Z}_m : \overline{a}+\overline{0}=\overline{a}.$
$\forall \overline{a}\in \mathbb{Z}_m : \overline{a}.\overline{1}=\overline{a}.$
Er is een unieke restklasse $\overline{x}$ met $\overline{a}+\overline{x}=\overline{0}$ , namelijk $\overline{x}=\overline{-a}$ .

Veronderstel dat we de rest willen bepalen van $73\times52$ bij deling door 7. Omdat $73 \equiv 3$ mod 7 en $52 \equiv 3$ mod 7, moet $73\times52 \equiv 3\times 3$ mod 7 $\equiv 9$ mod 7 $\equiv 2$ mod 7. Dus de rest bij deling van $73\times52$ door 7 is 2. We moeten daarvoor het product niet uitrekenen.