Modulair rekenen

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Modulair rekenen, of rekenen modulo een getal, is een vorm van geheeltallig rekenen met een getal dat als bovengrens fungeert, de modulus.

Bij modulair rekenen met modulus m of rekenen modulo m, wordt gerekend met de getallen 0, 1, 2, ..., 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 bij gewone berekening na deling door de modulus m. De normale definitie 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.

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

Definitie[bewerken]

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

a\equiv b \pmod 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 rond "mod n" ook wel worden weggelaten.

Voorbeelden[bewerken]

We rekenen modulo 7.

  • 5 x 4 ≡ 6 (mod 7). Bij gewoon rekenen is 5 x 4 = 20. De modulus is 7, dus we trekken zo vaak we kunnen 7 af van de uitkomst: 20-(2x7)=6. De rest is 6.
  • 4 x 4 ≡ 2 (mod 7). De modulus is 7. 16-(2x7)=2. De rest is 2.

Hieronder de vermenigvuldigingstabel die bij rekenen modulo 7 hoort:

× 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

Indien het gaat om decimale getallen wordt over het algemeen de decimale nauwkeurigheid van het deeltal genomen (maar dat is geen regel). Een lagere nauwkeurigheid is uitgesloten tenzij men het gebruik van afrondingen niet uitsluit (maar dat is in weinig situaties productief).

Voorbeeld:

  • 20,33/7 = 2,90.
    • De rest is 0,03 indien de gewenste nauwkeurigheidsgraad van het quotiënt twee decimalen is (conform die van het deeltal).
    • Wensen we echter een nauwkeurigheid tot drie decimalen dan geeft de deling het resultaat 2,904 met rest 0,002.
    • Zouden we ons tevreden stellen met een nauwkeurigheid van 0 of 1 decimaal dan is de rest 0,03 of afgerond 0. Een rest die minder nauwkeurig is dan het deeltal is absurd, tenzij het deeltal eerst afgerond wordt tot diezelfde nauwkeurigheid: 20/7 = 2 rest 6.

In veel programmeertalen is het teken voor modulus het procentteken (%).

Toepassing[bewerken]

Het bekendste voorbeeld van modulair rekenen is de tijdrekening in uren, 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 2n, 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 bankrekeningnummer 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 2-cijferig controlegetal te berekenen.

Algebra[bewerken]

Eenvoudig aangetoond kan worden dat (\mathbb{Z}/m\mathbb{Z}) algebraïsch gezien een ring is en wel een commutatieve ring met eenheidselement. 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. (Opgepast: wat men in Nederland een lichaam noemt, is in België een veld. Wat men in België een lichaam noemt, is in Nederland een scheeflichaam!)

Dit laatst kan als volgt worden aangetoond : uit de definitie van een priemgetal volgt dat een priemgetal m relatief priem is met alle getallen 1, ..., m-1 tussen 0 en m (want 1 is de enige deler van m die kleiner is dan m zelf). Met behulp van het algoritme van Euclides kan nu voor elke n tussen 1 en m de getallen x en y gevonden worden zodat nx + my = ggd(n,m)

Nu is de term my modulo m gelijk aan 0, want my /m = y rest 0. Verder geldt dat ggd(n,m) = 1, want n en m zijn relatief priem.

Dus modulo m een priemgetal is er voor elke n een x zodat nx = 1

Machtsverheffen[bewerken]

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

8^5 \equiv 3^5 \pmod 5
3^5\equiv 3\pmod 5
3^0\equiv 1\pmod 5

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

Voorbeeld en tegenvoorbeeld bij de stelling van Euler[bewerken]

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

3^{5-4}\equiv 3\pmod 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\equiv5\pmod {10} \mbox{  }, maar: 5^0\equiv1\pmod {10}

Zie ook[bewerken]