Modulorekenen

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.

dis

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.

Munten wegen

weegschaal We hebben 13 muntstukken, waarvan er eentje vals is. De enige manier waarop de valse muntzich van de echte munten onderscheidt is door zijn gewicht. We beschikken over een weegschaal zonder gewichtsaanduiding. Wat is het minimum aantal wegingen dat we moeten doen om te bepalen welke munt vals is? Gegeven een aantal munten waarvan er eentje vals is en gegeven zijn k wegingen. Je weet dat het valse muntstuk zwaarder is dan een echt muntstuk. Wat is maximum aantal muntstukken waaruit je zeker het valse kan identificeren? Wil je hierop het antwoord kennen, lees dan volgende tekst.