11.3A Delen in Zm

Inhoud van de pagina Delen in Zm:

Z.1 - a*b = 1 in Zm
Z.2 - Heeft ieder getal a wel een inverse in Zm?

 

Z.1 - a*b = 1 in Zm

a*b = 1 in Zm

Opgave 1

Los de volgende vergelijkingen op modulo 37:
a) 10x=1 (mod 37)
b) 10x=5 (mod 37)

 

Het oplossen van vergelijkingen waarin vermenigvuldigingen voorkomen zijn lastig en vragen in ieder geval veel werk. We kijken eens hoe we een dergelijke vergelijking oplossen als we niet modulo-rekenen.

Om de vergelijking 5*x=3 op te lossen deel je links en rechts door 5. Dit geeft x=3/5.
Delen door 5 is de omgekeerde bewerking van vermenigvuldigen met 5. In plaats van omgekeerde bewerking spreken we ook wel van inverse bewerking. Hiermee geven we duidelijk aan dat we de inverse bedoelen bij vermenigvuldigen.

De verzameling getallen {0,1,...m-1} duiden we aan met Zm. Vermenigvuldigen in Zm betekent vermenigvuldigen mod m
De inverse bij vermenigvuldigen met 5 in Z34 is 7.

Het oplossen van de vergelijking 5*x=3 in Z34 gaat nu als volgt:

5*x= 3(mod34)
7*5*x= 7*3(mod34)
1*x= 21(mod34)
x= 21(mod34)

Wat we nu in feite hebben geïntroduceerd is delen in Zm, of delen mod(m). We zullen echter nooit expliciet spreken over delen. Bij het oplossen van vergelijkingen delen we niet; we vermenigvuldigen met de inverse bij modulo-vermenigvuldigen.

Opgave 2

a) Ga na dat 10*6=1 in Z59.

Los de volgende vergelijkingen op in Z59:
b) 10= 4
c) 10= 5

We kunnen een oplossing van de vergelijking a*b = 1 in Zm gebruiken om vergelijkingen van de vorma*b c in Zm op te lossen. 
Daarnaast is de vergelijking a*b = 1 in Zm een hele belangrijke vergelijking in de cryptografie. 
In les 13 en 14 zullen we zien waarom dat zo is. Nu bekommeren we ons eerst om de vraag of de vergelijking wel voor iedere a en m een oplossing heeft.

We hebben nu gezien dat twee getallen elkaars inverse bij vermenigvuldiging heten als hun product 1 is. Er bestaan ook andere soorten inverses, maar die gebruiken we in deze lessenserie niet. We zullen daarom in het vervolg soms spreken over de "inverse" omdat het toch duidelijk is over wat voor een soort inverse we het hebben.

Als we niet modulo-rekenen, maar "gewoon" rekenen, is het niet moeilijk om bij een gegeven getal azijn inverse b te vinden zodat a*b = 1. Neem voor b het getal 1/a en je hebt een inverse van agevonden. Wanneer we modulo-rekenen is het niet zo eenvoudig. We rekenen daar immers alleen met gehele getallen en kunnen dus niet zomaar de omgekeerde van een getal nemen.

We gaan ons buigen over de volgende twee vragen. Ten eerste: heeft ieder getal a wel een inverse in Zm

Ten tweede: hoe vind je zo'n inverse? De eerste vraag beantwoorden we op de subpagina Z2, de tweede vraag in les 13

 

Z2 - Heeft ieder getal a wel een inverse in Zm?

Voorbeeld:
We gaan onderzoeken welke getallen een inverse hebben als we modulo 4 rekenen.
We zoeken bij a zijn inverse in Z4. Er moet dus gelden a*b=1.

a=0: Er is geen zodat 0*b = 1, want voor iedere geldt dat 0*b = 0, dus 0 heeft geen inverse in Z4.
a=1: Als b=1 staat er 1*1=1, dus is 1 een inverse van 1 in Z4.
a=2: 2*b is altijd even en dus nooit 1 in Z4, dus 2 heeft geen inverse in Z4.
a=3: Als b=3 staat er 3*3=1, want 9-2*4=1, dus is 3 een inverse van 3 in Z4.

Opgave 3

a) Welk getal heeft voor geen enkele m een inverse in Zm?
b) Welk getal heeft voor iedere m een inverse in Zm?

 

Opgave 4

a) In de volgende tabel rekenen we in Z5. Vul de inverse in als die er is.

 

Getal 0 1 2 3 4
Inverse          

b) In de volgende tabel rekenen we in Z6 Vul de inverse in als die er is.

Getal 0 1 2 3 4 5
Inverse            

c) In de volgende tabel rekenen we in Z7. Vul de inverse in als die er is.

Getal 0 1 2 3 4 5 6
Inverse              

d) In de volgende tabel rekenen we in Z8. Vul de inverse in als die er is.

Getal 0 1 2 3 4 5 6 7
Inverse                

e) In de volgende tabel rekenen we in Z9. Vul de inverse in als die er is.

Getal 0 1 2 3 4 5 6 7 8
Inverse                  

f) In de volgende tabel rekenen we in Z10. Vul de inverse in als die er is.

Getal 0 1 2 3 4 5 6 7 8 9
Inverse                    

g) In de volgende tabel rekenen we in Z11. Vul de inverse in als die er is.

Getal 0 1 2 3 4 5 6 7 8 9 10
Inverse                      

h) Heb je al een vermoeden wanneer wel een inverse in Zm heeft en wanneer niet? Zo ja, formuleer je vermoeden.

 

Opgave 5 

Als je de tabel bij opgave 4 goed hebt ingevuld, zie je dat steeds geldt dat de inverse van m - 1 inZm het getal m - 1 zelf is, dus dat (m - 1)2 = 1. Laat dit zien door (m - 1)2 uit te werken modm.

 

Wanneer de grootste gemene deler van twee getallen 1 is, noemen we deze getallen relatief priem.Deze getallen hebben dus geen andere positieve deler dan 1 gemeenschappelijk. Dit hoeft niet te betekenen dat de getallen priemgetallen zijn.

Opgave 6 

a) Noem een getal dat relatief priem is met 24.
b) Kan een even getal relatief priem zijn met 24?
c) Is ieder oneven getal relatief priem met 24?

 

Waarschijnlijk is het je in opgave 4 wel opgevallen dat a alleen een inverse in Zm heeft als a en mrelatief priem zijn, dat wil zeggen ggd(a,m)=1. Dat dit in het algemeen zo is volgt zullen we zien op de hoofdpagina.

Ga nu verder op de pagina 11.3 - Rekenen met inverse sleuter verder met opgave 2.