12.3A (a div m) en (a mod m)

Inhoud van deze pagina

E.1 Breukdeling en gehele deling
E.2 De rest bij deling
E.3 Somregel en productregel

 

E.1 Breukdeling en gehele deling

In les 1 heb je het verschil gezien tussen coderen en versleutelen. Doordat we het omzetten van rijtjes symbolen naar getallen (coderen) en omgekeerd (decoderen) op een van tevoren afgesproken manier gaan doen, kunnen we ons bij het beschrijven van de cryptosystemen beperken tot het werken met getallen. In de systemen die we in les 1 hebben bekeken, hadden we maar 26 symbolen en daarmee hadden we aan de getallen 0 tot en met 25 genoeg. De bewerkingen die we met deze getallen hebben uitgevoerd lieten zich eenvoudig informeel beschrijven. Nu we de beschikking hebben over meer symbolen en we ook nog gaan werken met rijtjes symbolen, krijgen we te maken met veel grotere getallen. En omdat we ons niet vast willen leggen op welke getallen er in onze boodschappen voor zullen komen, is het nodig wat gestructureerder naar de bewerkingen met gehele getallen te kijken.

Bij affiene cryptografie in les 2 was het nodig om bij elke uitkomst van een berekening te bepalen wat de rest bij deling door 26 was. Op die manier bestond zowel de onbewerkte als de versleutelde boodschap uit een rij van getallen uit de verzameling
0, 1, 2, 3, ..., 25. In deze subpagina wordt dat idee uitgebreid.

Hoeveel pootjes van 25 cm kun je zagen uit een balk van 240 cm? Het antwoord dat de rekenmachine geeft bij de deling 240:25 is in dit geval onzin: als je pootjes van 25 cm nodig hebt, dan heb je niets aan het laatste stukje dat toch te klein is. Als k het (grootste) aantal pootjes van 25 cm is dat we uit de balk van 240 cm kunnen zagen, dan is het grootste gehele getal dat voldoet aan 25*=240. In dit geval is dat dus 9.

Om onderscheid te maken tussen de 'breukdeling' en de 'geheeltallige deling'  noteren we 
de gehele deling als 240 div 5 (= 9)
en de breukdeling als 240:25 (= 9,6). 
Voor positieve gehele getallen a en m verstaan we onder a div m dus het geheel aantal keren dat m in a past.

Voor negatieve gehele getallen a is het wat lastiger in te zien wat a div m zou moeten zijn. Bij de positieve gehele a zochten we de grootste gehele k die voldeed aan k*m a. We spreken af dat we dat voor negatieve gehele a net zo doen.

Wanneer we (-240)div25 berekenen, komt daar dus -10 uit, want -10*25=-250 en dat is kleiner dan -240. De uitkomst -9 is niet goed, want -9*25=-225 en dat is meer dan -240.

Formeel kunnen we de operator div dus als volgt vastleggen:

Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*m = a.

Opgave 1 

Bereken:
a) 17 div 5.
b) 944 div 13.
c) 91 div 7.
d) (-22) div 7.

 

E.2 De rest bij deling

Zoals je bij het zagen van pootjes uit een balk in het algemeen iets overhoudt, blijft er bij geheeltallige deling in het algemeen een rest over. Bij deling van 25 door 7 is het resultaat 3. Maar 3*7 maakt de 25 niet vol. Er blijft als rest over: 25-3*7=25-21=4. Deze rest noteren we als 25 mod 7. 
We spreken dit uit als: "25 modulo 7". De rest van een geheel getal bepalen na deling door m, noemen we a reduceren modulo m.

In het algemeen is voor gehele getallen a en positieve gehele getallen m het getal amodm de rest bij geheeltallige deling van a door m. Formeel:

Voor gehele getallen en positieve gehele getallen m is
a mod m = a-m*(adivm) de rest bij geheeltallige deling van a door m

 

Opgave 2 

Bereken:
a) 17 mod 5.
b) 944 mod 13.
c) 91 mod 7.
d) (-22) mod 7.

 

De operatoren div en mod voldoen aan de volgende eigenschappen:

Voor gehele getallen a en positieve gehele getallen m geldt
(1) a = m*(a div m)+(mod m)
(2) ≤ a mod m < m


Opgave 3

a) Controleer deze eigenschappen voor a = 17 en = 5.
b) Controleer deze eigenschappen voor a = -22 en m =7.
c) Leg uit hoe deze twee eigenschappen volgen uit de definities van div en mod.

 

Als we berekeningen modulo een bepaald getal moeten uitvoeren, kunnen we gebruik maken van een aantal rekenregels. We zullen deze regels hier aan de hand van voorbeelden aannemelijk maken, maar ze niet bewijzen. In hoofdstuk 6 kom je precies te weten waarom de rekenregels kloppen.

 

Opgave 4

We hebben een balk van 240 cm en een balk van 190 cm en we gaan daar zo veel mogelijk pootjes van 25 cm afzagen.

a) Hoeveel cm houden we bij elke balk over?
b) Het is niet verrassend dat we dezelfde lengte overhouden. Waarom niet?

We zagen in deze opgave dat het verschil van twee getallen een veelvoud is van m als de twee getallen dezelfde rest hebben na deling door m. Dit resulteert in de volgende regel:

Voor gehele getallen a en b en positieve gehele getallen m geldt:
a(modm) =b(modm) precies dan als (a-b) modm= 0.


Opgave 5

a) Controleer deze eigenschap voor a=17, b=32 en m=5.
b) Laat zien dat het drietal a=22, b=35 en m=11 niet voldoet.
c) Geef een m zodanig dat het drietal a=22, b=35 en m wel voldoet.

 

Opgave 6 

We hebben een balk van 240 cm en een balk van 155 cm. We plakken de balken aan elkaar en zagen hier pootjes van 25 cm van.
a) Hoe lang is het stukje balk dat we uiteindelijk overhouden?

We doen hetzelfde nog een keer, maar nu met een balk van 190 cm en een balk van 305 cm.

b) Hoe lang is nu het stukje balk dat we uiteindelijk overhouden?
c) Leg uit waarom de uitkomsten bij a) en b) hetzelfde zijn.

 

Opgave 7 

We nemen 7 balken van 240 cm en zagen er pootjes van 25 cm van. Vervolgens plakken we alle restanten aan elkaar en zagen daar ook weer pootjes van 25 cm van.
a)Hoe lang is het stukje balk dat we uiteindelijk overhouden?

We doen hetzelfde met 7 balken van 190 cm.

b) Hoe bereken je makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?

Weer hetzelfde, dit keer met 32 balken van 240 cm.
c) Hoe bereken je nu makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?
d) Waarom doen die 25 balken extra er niet toe?

 

E.3 Somregel en productregel

In opgave 5 en 6 hebben we een idee gekregen hoe het optellen en vermenigvuldigen bij modulo-rekenen werkt. Inderdaad blijkt er een somregel en een productregel voor het modulo-rekenen te zijn:

Voor gehele getallen abc en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan

Somregel: (a+c) modm=(b+d) modm

Productregel: (a*c) modm=(b*d) modm


Opgave 8

Bereken de volgende uitdrukkingen. Doe dit zonder je rekenmachine te gebruiken en geef steeds aan welke rekenregel je gebruikt.
a) (123+456)mod10.
b) (113*222)mod10.
c) 17*(355+773)mod7.

Als we met de getallen 0 tot en met 25, de rangnummers van de 26 letters in het alfabet rekenen dan brengen we bij de rekenkundige bewerkingen (optellen en vermenigvuldigen) eigenlijk met behulp van modulo-rekenen het resultaat terug tot een getal in dit domein, ook al noemden we dat niet zo. De verzameling getallen {0,1,...m-1} duiden we aan met Zm.

Wanneer het duidelijk is dat we in Zm rekenen, en dus modulo m rekenen, laten we het "mod(m)" soms weg.

Voorbeeld:
Bereken 7*5 in Zm.
Berekening (7*5)mod12 = 35mod12 = 11 of 7*5 = 11.

Opgave 9 

Waarom kun je de berekening in bovenstaand voorbeeld niet opschrijven als 7*5 = 35 = 11?

Opgave 10 

Vul onderstaande tabellen in Zverder in.

+ 0 1 2 3 4   * 0 1 2 3 4  
0 0 1 2       0 0 0 0      
1 1 2         1 0 1        
2 2           2 0          
3             3            
4             4            


Opgave 11

Los de volgende vergelijkingen op:
a) In Z5: 3+= 1
b) In Z8: 3+x = 1
c) In Z19: 14+= 5
d) In Z19: 11+x = 0

Het oplossen van vergelijkingen van het type zoals in de vorige opgave zal niet zoveel problemen geven. Ook zonder dat je de hele opteltabel hebt uitgeschreven lukt het wel 14 +x = 5 op te lossen in Z19. In Z19 betekent 14 +x= 5 eigenlijk (14 +x) mod19 = 5 en dat wil zeggen dat je rest 5 overhoudt als je 14 +x door 19 deelt. Er is dus een k zodanig dat 14 + - 19*= 5, ofwel 9 +x= 19*k. Voor k=0 levert dit geen getal uit Z19; voor k=1 levert dit 9+x=19, dus x=10.

De berekening verloopt dus als volgt:
14+= 5 in Z19
(14+x)mod19 = 5
14+x-19*k = 5
9+x = 19k, dus x = 10 en =1

Misschien heb je het bij de opgave op een manier gedaan die je makkelijker vindt, maar bekijk ook de manier van redeneren hierboven goed.

Opgave 12 

Los de volgende vergelijkingen op bovenstaande manier op:
a) In Z23: 16+x = 7
b) In Z1278: 756+x = 341

Je ziet dat een vergelijking met een optelling oplossen niet zo moeilijk is. Wanneer er een vermenigvuldiging in de vergelijking zit, is een oplossing vinden minder eenvoudig. Een van de problemen is het volgende.

Als je niet modulo-rekent, kun je concluderen dat als ac = bc, dat dan daaruit a = b volgt. 

Bij modulo-rekenen geldt niet altijd dat als
a*cmb*c,dat dan amb(m staat voor "gelijkwaardig in Zm")

Opgave 13

a) Ga dit na voor a = 12, = 7, c = 6 en m = 10.
b) Leg uit waarom het in dit voorbeeld niet geldt.
c) Wat voor een getal moet zijn om wel te laten gelden dat ≡ mb als a*mb*c?

Afgezien daarvan is het ook lastig omdat je niet eenvoudig links en rechts door hetzelfde getal kunt delen.

Ga nu verder met les 12.3 opgave 6