Gehele getallen modulo m




Afspraken en gekende eigenschap van grootste gemene deler

In dit hoofdstuk stellen alle letters gehele getallen voor.
De grootste gemene deler van m en n noteren we als (m,n).
Als d = (n,m) dan zijn alle lineaire combinaties r.n + s.m van n en m veelvouden van d.
Als a een deler is van b, dan schrijven we a | b.

Definitie

Zij m een strikt positief getal

 
        a = b mod m
<=>
        m | (b - a)

In alles wat volgt, nemen we aan dat m een strikt positief getal is in een uitdrukking van de vorm 'modulo m' of 'mod m'.

Eigenschappen

De volgende eigenschappen volgen direct uit de definitie

 
Als     a = b mod m  en
        c = d mod m
Dan
        a+c = b+d mod m
        a-c = b-d mod m
        a.c = b.d mod m
        an  = bn    mod m   (met n > 0)
        n.a = n.b mod m

Vereenvoudigingsregel

 
Als      e is deler van  a, b en m
Dan geldt :
        a = b mod m  <=>  a/e = b/e mod m/e

Schrappingsregel

 
Als     (k,m) = 1
Dan
        ak = bk mod m <=>   a = b mod m

Bewijs:
 
        ak = bk mod m

<=>     m | (a-b)k
                        daar (k,m) = 1
<=>     m | (a-b)

<=>     a = b mod m

De vergelijking ax = b mod m

Oplossingsvoorwaarde

 
        ax = b mod m heeft een oplossing  x
<=>     Er is een k en een  x zodat ax - b = km
<=>     Er is een k en een x zodat ax - km = b
<=>     b is een lineaire combinatie van a en m
<=>     b is veelvoud van (a,m)
De laatste bewering geldt omdat alle lineaire combinaties van a en m juist de veelvouden zijn van (a,m)

ax = b mod m heeft een oplossing

<=>

b is een veelvoud van (a,m)


Vereenvoudigen van de vergelijking

Om de vergelijking ax = b mod m op te lossen, kijken we eerst of de oplossingsvoorwaarde vervuld is.

Nu is d = (a,m) deler van a, b en m. Dus kan de vergelijking vereenvoudigd worden tot

 
        ax/d = b/d mod m/d

<=>     a'x = b' mod m'   met (a',m')=1
Als (a',b') = k, dan kunnen we de schrappingsregel gebruiken om de laatste vergelijking te vereenvoudigen.

Voorbeeld:
18x = 6 mod 8

6 is een veelvoud van (18,8)=2 . De oplossingsvoorwaarde is vervuld.

De vereenvoudigingsregel geeft 9x = 3 mod 4 en nu geeft de schrappingsregel

3x = 1 mod 4

Het oplossen van de vergelijking

We veronderstellen dat de vergelijking oplosbaar is en reeds zoveel mogelijk vereenvoudigd is. We starten dus hier in de toestand
ax = b mod m met (a,m)=1.

Neem de (m-1) veelvouden van a
a ; 2a ; 3a ; ... ; (m-1)a
en neem al deze getallen modulo m.

Al deze veelvouden zijn verschillend!
Inderdaad, veronderstel een moment dat we zouden hebben:
3a = 5a mod m na het schrappen van a zou dan 3 = 5 mod m en dit is onmogelijk omdat 3 en 5 kleiner zijn dan m.

Dus al deze veelvouden van a zijn eigenlijk de getallen 1,2,3,...,m-1 in een willekeurige volgorde.

Hieruit volgt dat de vergelijking ax = b mod m juist 1 oplossing heeft modulo m.

In ons vorig voorbeeld proberen we x = 1, 2 en 3 en we vinden dat (3 mod 4) de oplossing is.

De vergelijking ax = 1 mod m

Nu bekijken we de vergelijking
 
        ax  = 1 mod m
De volgende stelling van Fermat geeft een oplossing voor een speciaal geval.

Stelling van Fermat

Als p priem is en (a,p)=1 dan is a(p-1) = 1 mod p.

Bewijs:
We hebben hierboven gezien dat als (a,p)= 1 de (p-1) veelvouden
a mod p ; 2a mod p ; 3a mod p ; ... ; (p-1)a mod p
gelijk zijn aan de getallen 1,2,3,...,p-1 in een willekeurige volgorde.

We maken producten van die getallen en we krijgen ,
(1a).(2a).(3a)...((p-1)a)= 1.2.3. ... .(p-1) mod p

Daar (1,p)=(2,p)=(3,p)=..(p-1,p)=1 , kunnen p-1 maal de schrappingsregel toepassen We krijgen dan

 
        a(p-1)   = 1 mod p

Euler functie phi

Zij m een strikt positief geheel getal.

phi(m) = het aantal strikt positieve gehele getallen n < m zodat (n,m)=1.

Eigenschappen van de Euler functie phi

Men kan bewijzen dat :

Als p priem is dan geldt: phi(p) = p-1 en phi(p2)=p.(p-1)

Als (a,b)=1 dan is phi(a.b) = phi(a).phi(b)


Veralgemening van de stelling van Fermat

Als (a,m) = 1 dan is aphi(m) = 1 mod m.

Bewijs:
Neem alle getallen b uit de verzameling {1, 2, ... m} waarvoor (b,m)=1.
Noem deze getallen b1, b2,..., bn. Dan is n = phi(m) .

Neem de veelvouden a.b1 mod m, a.b2 mod m, ..., a.bn mod m

Al deze getallen zijn verschillend want
Als bijvoorbeeld a.bi = a.bj mod m dan zal volgens de schrappingsregel gelden dat bi = bj mod m en dit is onmogelijk.

Bovendien is elk getal a.bi onderling ondeelbaar met m want a en bi zijn onderling ondeelbaar met m.

Daarom zijn deze n verschillende getallen
a.b1 mod m, a.b2 mod m, ...,a.bn mod m
de n verschillende getallen welke onderling ondeelbaar zijn met m.
Dus, deze getallen zijn b1, b2,... bn maar in een willekeurige volgorde.

Er geld dus: (a.b1)(a.b2)...(a.bn) = b1.b2. ... .bn mod m

Gebruik makend van de schrappingsregel krijgen we

 
        aphi(m)      = 1 mod m

De kleinste oplossing van ax = 1 mod m met (a,m) = 1

Zij n het kleinste strikt positief geheel getal zo dat
 
           an  = 1 mod m
Steunend op de de eigenschap van de deling kunnen we schrijven :
phi(m) = n.q + r met r < n of r = 0. Hieruit volgt
 
        1 = aphi(m) = an q + r = 1. ar mod m  => ar = 1 mod m
Dit is onmogelijk tenzij r = 0. Dus phi(m) = n.q + 0 en dan is n een deler van phi(m).

Besluit:

Het kleinste strikt positieve geheel getal n zo dat
 
           an  = 1 mod m
is een deler van phi(m).

Tweede methode om ax = b mod m op te lossen

We starten met de vereenvoudigde vergelijking ax = b mod m met (a,m)=1.
Dan kunnen we schrijven ,
 
              a. x = b mod m

           We vermenigvuldigen beide leden met aphi(m)-1

<=>     a. aphi(m)-1 . x = b . aphi(m)-1     mod m

<=>                 x = b.aphi(m)-1     mod m


      b.aphi(m)-1    mod m  is de unieke oplossing!

Stelsels vergelijkingen van de vorm x = a mod m

De behandeling van dit onderwerp vind je via deze link.


MATH-abundance - tutorial

Site adres is http://home.scarlet.be/math/nl/

Zend alle vragen, foutmeldingen en opmerkingen naar Johan.Claeys@ping.be
Het onderwerp of subject van de mail moet het woord 'wiskunde' bevatten omdat andere mails weggefilterd worden.