Dit algoritme is
oorspronkelijk door Euclides verzonnen om de grootste Gemene
Deler (GGD) van 2 getallen te vinden.
De werking is gebaseerd op twee vrij logische grondregels:
|
| 1. |
Als a deler is van b
dan is GGD(a,b) = a |
| 2. |
Als a = b m
+ n dan is GGD(a, b)
= GGD(b , n) |
|
|
|
De tweede regel maakt het mogelijk om de twee getallen
steeds kleiner te maken tot we de situatie vinden waarin de ene
een deler is van de andere. Dan zegt regel 1 dat we de gezochte
GGD hebben gevonden.
Een voorbeeldje zal een boel duidelijk maken, denk ik:
|
|
| Stel we zoeken de GGD van a =
2322 en b = 654 |
|
|
| 2322 = 654 3 + 360 |
|
| 654 = 360 1 + 294 |
|
| 360 = 294 1 + 66 |
|
| 294 = 66 4 + 30 |
|
| 66 = 30 2 + 6 |
|
| 30 = 5 6 |
|
Conclusie: de GGD van 2322 en 654 is 6.
Dat principe van "steeds zoveel mogelijk keer de ene van de
andere aftrekken" kunnen we ook gebruiken om van een gewone
breuk een kettingbreuk te maken, of om een rechthoek in
vierkanten te verdelen. Dat gaat z๓: |
Terug naar ons oorspronkelijke probleem.
Stel we zoeken gehele oplossingen van de vergelijking 37x
+ 20y = 1209.
Trek eerst overal zoveel mogelijk keer 20 van af. Van 37x
en 20y gaat dat 1 keer, van 1209 gaat dat 60 keer:
17x + 20(x + y - 60) = 9
Noem het getal tussen haakjes a, dan houden we
over: 20a + 17x
= 9 en a
= x + y - 60
Dit is een zelfde vergelijking als de
oorspronkelijke, alleen met kleinere co๋ffici๋nten. Laten we
daarom dezelfde truc nog een keer toepassen. Het kleinste getal is
17 geworden, dus nu trekken we overal zo vaak mogelijk 17 van af:
17(a + x) + 3a = 9
Noem het getal tussen haakjes b,
dan houden we over: 17b
+ 3a = 9 en b
= a + x
Deze stappen een aantal keer herhalen geeft achtereenvolgens:
|
