De ggd en het kgv

Rekenen met getallen: Rekenen met gehele getallen

De ggd en het kgv

Gehele getallen zijn op een getallenlijn te plaatsen, maar dit maakt ook duidelijk dat je ze kunt ordenen. Negatieve getallen staan links van de positieve getallen op de getallenlijn en het getal $1$ staat links van het getal $2$ op de getallenlijn, zoals uit onderstaande figuur te zien is.

Wanneer we op de getallenlijn naar rechts gaan worden gehele getallen groter, bijvoorbeeld het getal drie is groter dan het getal twee en dit noteren we als $3>2$ . Wanneer we op de getallenlijn naar links gaan worden gehele getallen kleiner, bijvoorbeeld $-3$ is kleiner dan $-2$ en dit noteren we als $-3<-2$ . Symbolen voor groter dan of gelijk aan en kleiner dan of gelijk aan zijn respectievelijk $\ge$ en $\le$ .

De ordeningsrelatie $\le$ heeft de volgende drie eigenschappen:

Antisymmetrie: voor alle gehele getallen $a$ en $b$ geldt: als $a\le b$ en $b\le a$ dan $a=b$ .
Transitiviteit: voor alle gehele getallen $a$ , $b$ en $c$ geldt: als $a\le b$ en $b\le c$ dan $a\le c$ .
Totaliteit: voor alle gehele getallen $a$ en $b$ geldt: $a\le b$ of $b\le a$ (of beide).

Ordening van natuurlijke getallen De ordening van gehele getallen induceert ook een ordening op de natuurlijke getallen door de ordeningsrelatie simpelweg te beperken tot deze getallen.

Met behulp van de ordeningsrelatie $\le$ op de verzameling van gehele getallen kun je voor elk tweetal getallen $a$ en $b$ het minimum en maximum definiëren: $\begin{aligned} \min(a,b)&= \begin{cases} a\quad\text{als }a\le b\\ b\quad\text{anders}\end{cases} \\ \\ \max(a,b)&= \begin{cases} b\quad\text{als }a\le b\\ a\quad\text{anders}\end{cases}\end{aligned}$

$\min(3,2)=2\qquad \max(3,2)=3\qquad\min(-3,-2)=-3\qquad \max(-3,-2)=-2$

Je kunt ook het minimum of maximum van drie of meer natuurlijke getallen definiëren. Laat $c$ een derde geheel getal zijn. Dan kun je de volgende definities hanteren: $\text{min}(a,b,c)=\text{min}\bigl(\text{min}(a,b), c\bigr)\qquad\text{en}\qquad \text{max}(a,b,c)=\text{max}\bigl(\text{max}(a,b), c\bigr)$

De ggd en het kgv Twee natuurlijke getallen kunnen niet-triviale delers gemeen hebben. De grootste gemene deler (ggd) is, zoals de naam als zegt, hun grootste gemeenschappelijke deler.

Bijvoorbeeld $2$ , $3$ en $6$ zijn delers van zowel $12$ en $18$ . De grootste gemene deler van $12$ en $18$ is $6$ . We noteren dit als $\mathrm{ggd}(12,18)=6$ .
De getallen $2$ en $3$ hebben allen $1$ als gemeenschappelijke deler en hun ggd is dus gelijk aan $1$ . We zeggen ook wel dat ze onderling ondeelbaar zijn. Meer in het algemeen, zeggen we het volgende:

Twee natuurlijke getallen heten onderling ondeelbaar als ze enkel en alleen $1$ als gemeenschappelijke deler hebben, d.w.z. als hun ggd gelijk is aan $1$ .

Het kleinste gemene veelvoud (kgv) van twee natuurlijke getallen is, zoals de naam als zegt, hun kleinste gemeenschappelijke veelvoud, dat wil zeggen het kleinste getal dat zowel een veelvoud van het ene getal, als van het andere getal is.

Bijvoorbeeld $36$ is zowel een veelvoud van $12$ als van $18$ en er is geen kleiner getal met deze eigenschap. We noteren dit als $\mathrm{kgv}(12,18)=36$ .

Naamgeving Het woord "gemeen" is archaïsch woordgebruik voor "gemeenschappelijk". Je komt het nog wel tegen in woorden als "gemeengoed".

$\begin{array}{lcllcr} \mathrm{ggd}(2,3)&=&1\qquad\qquad &\mathrm{kgv}(2,3)&=&6\\ \mathrm{ggd}(3,5)&=&1\qquad\qquad &\mathrm{kgv}(3,5)&=&15\\ \mathrm{ggd}(12,20)&=&4\qquad\qquad &\mathrm{kgv}(12,20)&=&60 \\ \mathrm{ggd}(0,4)&=&4\qquad\qquad &\mathrm{kgv}(0,4)&=&0 \end{array}$ We lichten één geval toe: de getallen $12$ en $20$ .

De delers van $12$ zijn $1$ , $2$ , $3$ , $4$ , $6$ en $12$ .
De delers van $20$ zijn $1$ , $2$ , $4$ , $5$ , $10$ en $20$ .
In dit geval zijn gemeenschappelijke delers $2$ en $4$ , en dus $\mathrm{ggd}(12,20)=4$ .

Veelvouden van $12$ zijn de getallen die deelbaar zijn door $12$ , dus: $12, 24, 36, 48, 60, 72,\ldots$
Veelvouden van $20$ zijn de getallen die deelbaar zijn door $20$ , dus: $20, 40, 60, 80, \ldots$
In dit geval zijn gemeenschappelijke veelvouden $60,120,180,\ldots$ , en dus $\mathrm{kgv}(12,20)=60$ .

Eigenschap De belangrijkste eigenschappen zullen we apart behandelen omdat ze een rol spelen bij het systematisch en efficiënt uitrekenen van ggd en kgv.

Laat $a$ en $b$ natuurlijke getallen zijn. Omdat $1$ een deler is van elk getal geldt: $1\le \mathrm{ggd}(a,b)\le \min(a,b)$ Per definitie van kleinste gemene veelvoud geldt en omdat $a\times b$ zowel een veelvoud van $a$ als van $b$ is geldt : $\max(a,b)\le \mathrm{kgv}(a,b)\le a\times b$

Je kunt ook de grootste gemene deler en het kleinste gemene veelvoud van drie of meer natuurlijke getallen definiëren. Laat $c$ een derde natuurlijk getal zijn. Dan kun je de volgende definities hanteren: $\mathrm{ggd}(a,b,c)=\mathrm{ggd}\bigl(\mathrm{ggd}(a,b), c\bigr)\qquad\text{en}\qquad \mathrm{kgv}(a,b,c)=\mathrm{kgv}\bigl(\mathrm{kgv}(a,b), c\bigr)$

De ggd en kgv kun je ook voor gehele getallen definiëren en dit levert altijd niet-negatieve getallen op. In feite speelt het minteken in de definitie van ggd en kgv geen enkele rol omdat de volgende eigenschappen voor gehele getallen $a$ en $b$ gelden: $\begin{array}{ccccccc}\mathrm{ggd}(a,b)&=&\mathrm{ggd}(-a,b)&=&\mathrm{ggd}(a,-b)&=&\mathrm{ggd}(-a,-b)\\ \mathrm{kgv}(a,b)&=&\mathrm{kgv}(-a,b)&=&\mathrm{kgv}(a,-b)&=&\mathrm{kgv}(-a,-b)\end{array}$

Laat $a$ en $b$ natuurlijke getallen zijn. Dan zijn onderstaande beweringen voor de ggd en het kgv juist.

$\mathrm{ggd}(a,b)= \mathrm{ggd}(b,a)$ .
Als $c$ een gemeenschappelijke deler is van $a$ en $b$ dan $\mathrm{ggd}(a,b)= c\times \mathrm{ggd}\left(\frac{a}{c},\frac{b}{c}\right)$ .
Als $a=q\times b+r$ , d.w.z. als deling van $a$ door $b$ de rest $r$ oplevert, dan $\mathrm{ggd}(a,b)=\mathrm{ggd}(b,r)$ .
$\mathrm{ggd}(a,b)$ is gelijk aan het product van de hoogste machten van de priemgetallen die zowel $a$ als $b$ delen.
$\mathrm{kgv}(a,b)$ is gelijk aan het product van de hoogste machten van de priemgetallen die $a$ of $b$ (of beide) delen.
$\mathrm{ggd}(a,b)\times\mathrm{kgv}(a,b)=a\times b$ .

We nemen als voorbeeld $a=2\times 3^2\times 5 \times 7=630$ en $b=2^2\times3^3\times 5=540$ .

Als de priemontbindingen van $a$ en $b$ bekend zijn, dan leveren de rekenregels 4 en 5 bijna onmiddellijk de ggd en kgv op. Uit $\begin{array}{rcccccccc} 630&=&2&\times&3^2&\times&5&\times&7\\ 540&=&2^2&\times&3^3&\times& 5&&\end{array}$ lezen we af en concluderen we $\begin{array}{rcccccccccr} \mathrm{ggd}(630,540)&=&2&\times&3^2& \times& 5 &&&=&90\\ \mathrm{kgv}(630,180)&=& 2^2&\times& 3^3&\times& 5&\times& 7&=&3780\end{array}$

In dit voorbeeld levert regel 2 ook snel de ggd op omdat je gelijk ziet dat 10 een deler van de twee getallen is. Dus: $\mathrm{ggd}(630,540)=10\times \mathrm{ggd}(63,54)=10\times 9\times\mathrm{ggd}(7,6)=10\times 9\times1=90$ De kgv kun je dan met regel 6 bepalen: $\mathrm{kgv}(630,540)=\frac{630\times 540}{\mathrm{ggd}(630,540)}=\frac{630\times 540}{90}=7\times 540=3780$

Het basisidee achter regel 3 is dat de ggd van twee getallen ook een deler is van het verschil van deze twee getallen. Bijvoorbeeld is $\mathrm{ggd}(630,540)$ ook een deler van $630-540=90$ en dan ben je er al omdat $90$ deler is van zowel $630$ als $540$ .

Regel 3 vormt de basis van de meest efficiënte en systematische methode om de ggd uit te rekenen, namelijk het Euclidisch algoritme.

Bepaal de grootste gemene deler (ggd) en het kleinste gemene veelvoud (kgv) van $213$ en $324$ via de priemontbindingen van deze getallen.

$\mathrm{ggd}(213,324)={}$ $3$
$\mathrm{kgv}(213,324)={}$ $23004$

De priemontbindingen van de gegeven getallen zijn: $213 = 3\times 71 \qquad\text{en}\qquad 324 =2^2\times 3^4$ Voor de ggd nemen we het product van de hoogste machten van de priemgetallen die zowel $213$ en $324$ delen. Voor het kgv nemen we het product van de hoogste machten van de priemgetallen die $213$ of $324$ (of beide) delen. Dus:
$\begin{aligned} \mathrm{ggd}(213,324) &= 3\\ \\ \mathrm{kgv}(213,324) &= 2^2\times 3^4\times 71\\&=23004 \end{aligned}$

Nieuw voorbeeld

Laat $a$ en $b$ twee natuurlijke getallen zijn met $a\ge b$ (als niet aan de ordeningsrelatie voldaan is verwissel je gewoon de twee getallen). De ggd van $a$ en $b$ kan nu als volgt worden berekend:

Bereken de rest $r$ van $a$ bij deling door $b$ .
Vervang $a$ door $b$ en $b$ door $r$ .
Herhaal de voorafgaande stappen totdat $b$ gelijk is aan $0$ .
De laatste waarde van $a$ is gelijk aan $\mathrm{ggd}(a,b)$ .

$\begin{array}{rcllcl}\mathrm{ggd}(999,195) &=& \mathrm{ggd}(195,24) & \blue{\text{omdat}\;\;\;999}&\blue{=}&\blue{5\times 195+24}\\ &=& \mathrm{ggd}(24,3) & \blue{\text{omdat}\;\;\;195}&\blue{=}&\blue{8\times 24+3}\\ &=& \mathrm{ggd}(3,0) & \blue{\text{omdat}\;\;\;\;24}&\blue{=}&\blue{8\times 3+0}\end{array}$ Dus: $\mathrm{ggd}(999,195)=3$ .

Voor natuurlijke getallen $a$ en $b$ geldt dat er getallen $x$ en $y$ te vinden zijn zodanig dat $\mathrm{ggd}(a,b)=x\times a + y\times b$ . De getallen $x$ en $y$ zijn niet uniek.

Een voorbeeld legt uit hoe $x$ en $y$ bepaald kunnen worden. Via het Euclidisch algoritme hebben we $\begin{array}{rcllcl}\mathrm{ggd}(999,195) &=& \mathrm{ggd}(195,24) & \blue{\text{omdat}\;\;\;999}&\blue{=}&\blue{5\times 195+24}\\ &=& \mathrm{ggd}(24,3) & \blue{\text{omdat}\;\;\;195}&\blue{=}&\blue{8\times 24+3}\\ &=& \mathrm{ggd}(3,0) & \blue{\text{omdat}\;\;\;\;24}&\blue{=}&\blue{8\times 3+0}\end{array}$ Dus: $\begin{array}{rcl}999&=&5\times 195+24\\ 195&=&8\times 24+3 \\ 24&=&8\times 3+0\end{array}$ Nu gaan we vanaf de één na onderste rij steeds een rij omhoog, waarbij we die rest invullen.
Uit $195=8\times 24+3$ volgt dat $3= 195-8\times 24$ .
Uit $999=5\times 195+24$ volgt dat $24=999-5\times 195$ en substitutie in $3= 195-8\times 24$ geeft $3= 195-8\times (999-5\times 195)=41\times195-8\times 999$ .
Dus: $3=\mathrm{ggd}(999,195)=-8\times 999+41\times 195$ Dit is geen unieke relatie want bijvoorbeeld geldt ook $3=\mathrm{ggd}(999,195)=187\times 999-958\times 195$

Bereken de grootste gemene deler (ggd) van $157$ en $22$ via het Euclidisch algoritme.

Het Euclidisch algoritme verloopt als volgt: $\begin{array}{rcllcl}\mathrm{ggd}(157,22) &=& \mathrm{ggd}(22,3) & \blue{\text{omdat}\;\;\;157}&\blue{=}&\blue{7\times 22+3}\\ &=& \mathrm{ggd}(3,1) & \blue{\text{omdat}\;\;\;22}& \blue{=}& \blue{7\times 3+1}\\ &=& \mathrm{ggd}(1,0) & \blue{\text{omdat}\;\;\;3}&\blue{=}&\blue{3\times 1+0}\\ &=& 1&&&\end{array}$

Nieuw voorbeeld