Stelsels lineaire congruenties




Afspraak

In de onderstaande paragrafen werken we enkel met gehele getallen en alle namen, zoals a, b, x, m, n, ... , stellen gehele getallen voor. Ook de variabelen bewegen zich in de verzameling van de gehele getallen.

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'.

Doelstelling

Deze pagina leidt tot een algemene methode om stelsels op te lossen van de vorm
 
   / x = a mod m
   \ x = b mod n

     met ggd(m,n) = 1
Na kennismaking met enkele inleidende begrippen wordt stapsgewijs een gedachtengang opgebouwd welke uiteindelijk leidt tot een algemene methode voor het oplossen van dergelijke stelsels.

Eigenschap van de grootste gemene deler van twee gehele getallen

De grootste gemene deler van m en n noteren we ggd(m,n).

Men kan aantonen dat de grootste gemene deler d van twee getallen m en n altijd kan geschreven worden als lineaire combinatie van m en n. Dit betekent dat er altijd gehele getallen r en s bestaan zodat d = r.m + s.n

Voorbeeld:
ggd(12, 40) = 4 ; Dus 4 moet te schrijven zijn als lineaire combinatie van 12 en 40.
Een lineaire combinatie is -3.(12) + 1.(40) = 4

Onderling ondeelbare getallen

Twee getallen m en n heten onderling ondeelbaar als en slechts als hun grootste gemene deler 1 is.
 
   m en n onderling ondeelbaar
<=>
    ggd(m,n) = 1
Er bestaan dan gehele getallen r en s zodat r.(m) +s.(n) = 1.

Voorbeeld :

ggd(3,5) = 1
Een lineaire combinatie is 2.(3) - 1.(5) = 1

De verzameling ( a modulo m )

Definitie:

(a modulo m) is de verzameling van alle gehele getallen van de vorm (a + een m-voud)

Notatie : a mod m

Voorbeelden :

 
      43 behoort tot de verzameling  3 mod 4 want 43 is (3 + een viervoud)

      a mod 4 = b mod 4  <=> (b-a) is een 4-voud

      3 mod 4 = 15 mod 4  want 15 -3 is een 4-voud

Belangrijke notatie-afspraak

 
   Als een getal b behoort tot de verzameling  a mod m dan schrijven we

        b = a mod m

   en dit is gelijkwaardig met

        b = (a + een m-voud)

De vergelijking x = 3 mod 4

 
   Beschouw  de vergelijking x = 3 mod 4  met onbekende x.

        x = 3 mod 4 betekent   x = (3 + een viervoud)
De vergelijking heeft oneindig veel oplossingen voor x .

Stelsels van twee vergelijkingen

 
  /  x = 2 mod 6
  \  x = 5 mod 7
In dit stelsel wordt gevraagd naar de gehele getallen x zodat
 
   x is (2 + een 6-voud) en x is ook (5 + een 7-voud)

   Er wordt dus gevraagd naar de doorsnede van de verzamelingen 2 mod 6 en 5 mod 7.
De oplossingenverzameling ligt niet voor de hand.

In volgende paragrafen zullen we aantonen hoe dergelijke stelsels opgelost kunnen worden. We vermelden niet alleen de werkwijze maar we tonen ook de gedachtengang die leidt tot die werkwijze.

Het homogeen stelsel

Gegeven zijn twee onderling ondeelbare getallen m en n. Beschouw het stelsel van twee vergelijkingen
 
 /  x = 0 mod m
 \  x = 0 mod n        (1)
De eerste vergelijking betekent: x = (0 + een m-voud) of korter x = een m-voud.

De tweede vergelijking betekent: x = (0 + een n-voud) of korter x = een n-voud.

De oplossingenverzameling van het stelsel is de verzameling van de gemene veelvouden van m en n. Daar m en n onderling ondeelbaar zijn, zijn de gemene veelvouden van m en n, alle veelvouden van (m.n).
De oplossingenverzameling van het stelsel is ( 0 mod m.n )

Het niet homogeen stelsel

Gegeven zijn twee onderling ondeelbare getallen m en n. Beschouw het stelsel van twee vergelijkingen
 
 /  x = a mod m
 \  x = b mod n         (2)

Hulpstelling

Als x' een gekende oplossing is van het stelsel (2),
Dan is de verzameling V = x' mod m.n de oplossingenverzameling van het stelsel (2).

Bewijs:

  1. We tonen aan dat elk element van V een oplossing is van stelsel (2)

    Een element x" van V is te schrijven in de vorm x' + k.m.n

     
    We weten dat     x' = a mod m
    
    dan is ook       x' + (k.n).m = a mod m
    
    vandaar dat ook  x" = a mod m    (3)
    
    --------------------------------
    
    We weten dat     x' = b mod n
    
    dan is ook       x' + (k.m).n = b mod n
    
    vandaar dat ook  x" = b mod n     (4)
    
    --------------------------------
    
    Uit (3) en (4) volgt dat x" een oplossing is van  stelsel (2)
    
    
  2. We tonen aan dat een willekeurige oplossing van stelsel (2) een element is van V

    Noem x" een willekeurige oplossing van het stelsel (2)
    Dan geldt :

     
          x' is (a + een m-voud)  en x" is (a + een m-voud)x'
    
    =>   (x"-x') is een m-voud
    
    =>    x" - x' = 0 mod m        (5)
    
    en ook
    
          x' is (b + een n-voud)   en x" is (b + een n-voud)
    
    =>    (x"-x') is een n-voud
    
    =>     x" - x' = 0 mod n       (6)
    
    
    Uit (5) en (6) volgt
    
           x" - x' is  een oplossing van het homogeen stelsel (1)
    
    Maar , de oplossingenverzameling van dat  stelsel (1) is  ( 0 mod m.n )
    
    Hieruit volgt
    
        x" - x' = 0 mod m.n
    <=>
        x" - x' is een (m.n)-voud
    <=>
        x" = x' + een (m.n)-voud
    <=>
        x" = x' mod m.n
    <=>
        x" is een element van V
    

De Chinese reststelling

Gegeven :
  • Twee onderling ondeelbare getallen m en n.
    Daar ggd(m,n) = 1, bestaan er getallen r en s zodat r.m +s.n = 1.

  • Het stelsel
     
     / x = a mod m
     \ x = b mod n         (2)
    
Te bewijzen :

De oplossingenverzameling van het stelsel is (a.s.n + b.r.m) mod m.n


Bewijs:

We weten dat 1 = r.m + s.nr.m + s.n - 1 = 0
en daaruit volgt r.m + s.n - 1 = 0
Er geldt :

 
     0 is een m-voud

=>   r.m+s.n -1 is een m-voud

=>   s.n -1 is een m-voud

=>   s.n = 1 mod m

en ook

     0 is een n-voud

=>   r.m+s.n -1 is een n-voud

=>   r.m -1 is een n-voud

=>   r.m = 1 mod n

Hieruit volgt dan

     s.n = 1 mod m   =>  a.s.n = a mod m
en
     r.m = 1 mod n   =>  b.r.m = b mod n

maar dan geldt ook

     a.s.n + b.r.m  = a mod m
     a.s.n + b.r.m  = b mod n
a.s.n + b.r.m is dus een gekende oplossing van het algemeen niet homogeen stelsel (2).

Steunend op de hulpstelling weten we nu :

(a.s.n + b.r.m) mod m.n is de oplossingenverzameling van het stelsel (2)

Voorbeeld

 
   / x = 2 mod 6
   \ x = 5 mod 7
Dus m = 6 en n = 7 ; a = 2 en b = 5.
(-1).6+1.7 = 1 ; neem r = -1 en s = 1.

Dan is a.s.n + b.r.m = -16

-16 mod 42 is de oplossingenverzameling van het stelsel

Toepassing

Bereken de gemeenschappelijke nulpunten van de functies sin( pi.(x-5)/3 ) en cos( pi(x-7)/16 )

Stelsels met meer dan twee vergelijkingen

De methode hierboven kan trapsgewijs uitgebreid worden. Een stelsel van 3 vergelijkingen wordt teruggebracht tot twee, enzovoort...

Als 3 vergelijkingen kunnen herleiden naar twee, kunnen we in principe al dergelijke stelsels oplossen.

We tonen de methode aan de hand van een voorbeeld.

 
 x = 2 mod 6
 x = 5 mod 7
 x = 3 mod 5
We lossen eerst het stelsel van de eerste twee vergelijkingen op. Men vindt de oplossingen -16 mod 42.
Om de oplossingen van het stelsel te vinden moeten we volgend stelsel nog oplossen :
 
 x = -16 mod 42
 x = 3 mod 5
Dit is opnieuw iets wat we al kunnen oplossen. De oplossingen zijn
 
  68 mod 210.
Let op : dit is maar correct doordat 6, 7 en 5 twee aan twee onderling ondeelbaar zijn.


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.