© h.hofstede (h.hofstede@hogeland.nl)

Delers en Veelvouden.
       
Na een aantal afspraken in de vorige les begint nu pas de echte getaltheorie.
Door alleen maar getallen bij elkaar op te tellen of van elkaar af te trekken valt er niet zo heel veel spannends te beleven. Het blijven allemaal "stapjes op de getallenlijn".
Het wordt interessanter als we het vermenigvuldigen van getallen gaan bekijken. Dat vertelt ons iets meer over de "structuur" van de getallen. Eén van de belangrijkste begrippen uit de getaltheorie is daarom het begrip "Deler":
       

a is deelbaar door b als er een geheel getal k bestaat zodat  a = k  • b 

       
In dat geval heet b een deler van a,  en is a een veelvoud van b. We noteren dat als  b | a.
Als een getal een veelvoud van 2 is, dan noemen we dat getal even.
Een aantal simpele gevolgen zijn direct:
• 0 is een even getal
• Als  b | a  en  a | b,  dan is  a = ± b
• Als twee getallen a en b de zelfde delers hebben, dan is a = ± b
       
Maar er zijn ook best ingewikkeldere stellingen over delers te maken.
       
Stelling:  

Deelbaarheid is transitief
       
Dat wil zeggen:  als  a | b en  b | c  dan is ook  a | c.
Bewijs:
  b | c  dus  c = k • b
a | b  dus  b = m • a
dus  c = k • b = k • (m • a) = (k • m) • a = n • a  dus  a is een deler van c
q.e.d.  
       
Als x en y gehele getallen zijn, dan noemen we   ax + by  een lineaire combinatie van a en b, en dan geldt:
       
Stelling:  

Als  d | a  en   d | b   dan deelt d elke lineaire combinatie van a en b   

       
Bewijs:  
  d | a  en   d | b  dus  a = k • d  en  b = m • d
dan is  ax + by = (kd)x  + (md)y  =  kdx + mdy = d(kx + my)  en omdat kx + my  geheel is,
is d dus een deler van ax + by 
q.e.d.  
       
Rest en Quotiënt.
       
Definitie:
Stel dat voor gehele getallen  a en b  met  b ≠ 0  geldt  a = bq + r  met 0 ≤  r < |b|
Dan noemen we  q het quotiënt en r de rest  bij deling van a door b.
De rest van een getal bij deling door 2 noemen we ook wel de pariteit  van dat getal, en die is dus 0 of 1.
       
Stelling:

Bij elk paar gehele getallen a en b met b ≠  0  bestaat er precies één quotiënt en één rest.
       
Bewijs:  
  Stel dat er twee verschillende quotiënten  q1 en q2  en twee verschillende resten  r1  en r2  zijn.
a = bq1 + r1  en  a = bq2 + r2
Dan is  r1 - r2 = (a - bq1) - (a - bq2) =  -bq1 + bq2 = b(q2 - q1)  dus r1 - r2  is deelbaar door b  dus r1 - r2 = kb 
r1 = kb + r2  dus als  k ≥ 1 dan is  r1 > b  (want r2 ≥ 0)  en dat kan niet vanwege de definitie van rest.
r2 = r1 - kb  dus als  k ≤ -1  dan is  r2 > b  (want  r1 ≥ 0) en dat kan niet vanwege de definitie van rest.
Dus moet wel gelden k = 0  en dus is  r1 = r2 = r
Maar dan is bq1 + r  = bq2 + r  dus   bq1 = bq2   dus   q1 = q2 = q  want  b ≠ 0

OK, nu nog even bewijzen DAT er altijd een q en een b bestaan.

Neem eerst  b > 0
a/b is een reëel getal, dus het ligt tussen twee gehele getallen in 
(als a/b een geheel getal is zijn we meteen al klaar want dan is  q = a/b en r = 0).
Dus er bestaat een q zodat  q  ≤ a/b  <  q + 1  dus  bq ≤ a  < bq + b   (dat mag want  b > 0)
Dus  0 ≤ a - bq  < b
Neem nu gewoon r = a - bq  dan heb je twee getallen r en q die precies aan de voorwaarden van rest en quotiënt voldoen

Op dezelfde manier gaat het als je neemt  b < 0.
q.e.d.    
       
We kunnen nu de allereerste definitie van deelbaarheid vereenvoudigen:
       

a is deelbaar door b als a rest 0 heeft bij deling door b

       
Grootste Gemene Deler.
       
Definitie 1.
De Grootste Gemene Deler van een aantal getallen is het grootste getal dat een deler is van al die getallen.
We noteren dat als  GGD{a1, a2, ...,an}

Definitie 2
Als GGD{a1, a2} = 1  dan noemen we de getallen a1 en a2  onderling ondeelbaar  of  copriem  of  relatief priem.

Stelling van Bézout.
       

Als a1 en a2 gehele getallen zijn, dan is  GGD{a1, a2}  een lineaire combinatie van  a1 en a2
       
Bewijs.    
 
Noem de verzameling van alle lineaire combinaties van a en b de verzameling V. Omdat a en b niet beiden nul zijn, is er zeker een element van V te vinden dat groter is dan nul.

Noem het kleinste positieve element van V het getal m.  Dus m = ax + by

Stel dat q en r het quotiënt en de rest zijn van deling van a door m.
Dan is   a = mq + r  met 0 ≤  r <  m  (definitie van q en r)
Dus a = (ax + by)q + r  =  axq + byq + r 
Daaruit volgt  r = a(1 - xq) - by dus  r is een lineaire combinatie van a en b en zit dus in V.
Maar als  r  > 0 is, dan is dus  r ≥  m  (immers m was de kleinste positieveling in V).
Dat is strijdig met het feit dat   r <  m, dus moet gelden r = 0  dus is m een deler van a.


Op precies dezelfde manier bewijs je dat m ook een deler van b is, dus m is een gemeenschappelijke deler van a en b

Stel dat er nog een andere gemeenschappelijke deler n van a en b is, dus dat  a = q1• n en b = q2• n
Dan is m =  ax + by = q1nx  + q2ny = n(q1x + q2y).
Dus n is een deler van m  dus  n < m  (ze waren ongelijk).
Dus m is de grootste gemende deler van a en b.
q.e.d.    
       
Deze stelling van Bézout heeft een paar snelle directe gevolgen.
       
Gevolg 1. Als c | a  en   c | b  dan is  c | GGD(a, b)
    (immers c deelt elke lineaire combinatie van a en b dus ook GGD(a, b))
Gevolg 2. ggd(a, b) is de kleinst mogelijke strikt positieve lineaire combinatie van a en b
    (immers GGD(a, b) deelt elke lineaire combinatie ervan. Dus als ax + by > 0, dan is GGD(a, b) ≤ ax + by )
Gevolg 3. Elk veelvoud van GGD(a, b) is een lineaire combinatie van a en b
    (immers  als  c = k • GGD(a, b) = k(ax + by) dan is c dus een lineaire combinatie van a en b)
       
Er is trouwens ook nog een algemenere stelling van Bézout:
 

Als {a1, a2, ..., an}  gehele getallen zijn, dan kan de GGD(a1, a2, ..., an}
geschreven worden als lineaire combinatie van a1, a2, .... , an.

       
Tot zover de theorie achter de GGD.
In de volgende les zullen we bekijken hoe je zo'n GGD het handigst op kunt sporen.
 
       

© h.hofstede (h.hofstede@hogeland.nl)