Modulair rekenen

Uit Wikipedia, de vrije encyclopedie

Modulair rekenen, of rekenen modulo een getal, is een vorm van geheeltallig rekenen met een 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 of gelijk is 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.

Het rekenen met modulus m of ook modulo m wordt wiskundig wel aangeduid als ( $\mathbb{Z}/m\mathbb{Z}$ ).

[bewerk] Voorbeelden

We rekenen modulo 7.

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

4x4=2 mod 7. De modulus is 7. 16-(2x7)=2. De rest is 2.

Hieronder de vermenigvuldigingstabel die bij rekenen modulo 7 hoort:

×	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	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 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 (%).

[bewerk] Toepassing

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. Ook elke computer rekent modulair met modulus 2ⁿ, waarbij n het aantal bits in een variabele is.

[bewerk] Algebra

Eenvoudig aangetoond kan worden dat ( $\mathbb{Z}/m\mathbb{Z}$ ) algebraïsch gezien een ring is en wel een commutatieve ring met één-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.

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

[bewerk] Machtsverheffen

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

$3^5\equiv 3\hbox{ mod 5}$

$3^0\equiv 1\hbox{ mod 5}$

Wel geldt de volgende stelling van Euler: de exponent mag herleid worden modulo de Euler-indicator $\varphi(m)$ van m. De Euler-indicator van 5 is 4, en inderdaad is