Het Euclidisch Algoritme

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

           
Een algoritme moet je zien als een soort "recept".
Nou bedacht de Griekse Euclides een "recept" om van twee willekeurige getallen het grootste getal op te sporen waar beiden door gedeeld kunnen worden. Dat getal heet de Grootste Gemene Deler (GGD).

Stel bijvoorbeeld dat we graag willen weten wat het grootste getal is waar we 1470 en 825 door kunnen delen.
Je ziet natuurlijk zσ dat je beiden door 5 kunt delen, maar misschien is er wel een groter getal waar je beiden σσk door kunt delen.

't Is eigenlijk heel eenvoudig die GGD te vinden, maar je moet er maar opkomen....

Stel dat we de GGD van 1470 en 825 weten......
Laten we die mysterieuze GGD als een blauw blokje tekenen.
Dan kun je dus 1470 en 825 beiden zien als een ketting van blokjes die allemaal de grootte van die onbekende GGD hebben:
           

           
(het aantal blokjes in die twee kettingen is voorlopig natuurlijk nog onbekend)
Daarbij is het de vraag hoe we er achter kunnen komen hoe groot zo'n mysterieus blauw blokje is.
Nou, als we daarnaar op zoek gaan, dan kunnen we ons vraagstuk kleiner maken door de onderste blauwe rij van de bovenste af te trekken:
           

           
Haal eerst maar eens al die rooien weg! Daar wordt het probleem tenminste alvast iets kleiner door. Dan houden we het volgende over (1470 - 825 = 645, maar dat wist je natuurlijk wel)
           

           
Ik hoop dat je al door hebt waar dit naar toe gaat:  trek nu die 645 van de 825 af, en je houdt 180 over:
           
           
En nu kun je zelfs in plaats van ιιn keer die 180 van de 645 af te trekken, dat meteen drie keer doen, immers 180 past drie keer in 645. Dat gaat wel zo snel!
           
           
Dat geeft  (645 - 3 • 180 = 105)
 
 
nog een paar keer van elkaar aftrekken, en je krijgt dit:
 
           
En daar is ons mysterieuze blokje al!! Het is 15 !!!

Wat is hier gebeurd?

We hebben elke keer van twee getallen een nieuw getal gemaakt door de kleinste zo vaak mogelijk van de grootste af te trekken. Dat zag er zσ uit:
           
overgebleven: verkleinen:
1470 en 825:   1470 - 1 • 825 = 645
825 en 645: 825 - 1 • 645 = 180
645 en 180: 645 - 3 • 180 = 105
180 en 105: 180 - 1 • 105 = 75
105 en 75: 105 - 1 • 75 = 30
75 en 30: 75 - 2 • 30 = 15
30 en 15: 30 - 15 = 15
15 en 15: 15 - 15 = 0
           
In een blokschema zou Euclidisch Algoritme er zσ uit kunnen zien:
           

           
Het Uitgebreid Euclidisch Algoritme.

Het Euclidisch Algoritme kun je uitbreiden om een oplossing van de vergelijking  a • x + b • y = ggd(x, y) te vinden. Dat wil zeggen, bij gegeven x en y kun je de coλfficiλnten a en b vinden
Ik denk dat een voorbeeld wel zal duidelijk maken hoe het werkt.

Neem x = 1452 en y = 735.
Dan vinden we de GGD daarvan als volgt, waarbij we het verkleinen bij het Euclidisch algoritme als vermenigvuldiging plus rest noteren:
           
1452
735
717
18
15  		= 1 • 735 + 717
= 1 • 717 + 18
= 39 • 18 + 15
= 1 • 15 + 3
= 5 • 3 + 0
GGD 3
           
Dat geeft ons de mogelijkheid getallen a en b te vinden waarvoor de vergelijking   1452a + 725b = 3 klopt.
Maak eerst een nieuwe kolom met daarin de rest voorop geschreven:
           
1452
735
717
18
15  		= 1 • 735 + 717
= 1 • 717 + 18
= 39 • 18 + 15
= 1 • 15 + 3
= 5 • 3 + 0
1452
735
717
18
15		 = 717 + 1 • 735
= 18 + 1 • 717
= 15 + 39 • 18
= 3 + 1 • 15
= 0 + 3 • 5
           
Nu gaan we vanaf de ιιn na onderste rij steeds een rij omhoog, waarbij we die rest invullen:
           
 
1452
735
717
18
15  		= 1 • 735 + 717
= 1 • 717 + 18
= 39 • 18 + 15
= 1 • 15 + 3
= 5 • 3 + 0
717
18
15
3
0		 = 1452 - 1 • 735
= 735 - 1 • 717
= 717 - 39 • 18
= 18 - 1 • 15
= 15 - 3 • 5




 		 3 = 40 • 735 - 41 • (1452 - 1 • 735) = 81 • 735 - 41 • 1452
3 = 40 • (735 - 1 • 717) - 1 • 717 = 40 • 735 - 41 • 717
3 = 18 - 1 • (717 - 39 • 18) = 40 • 18 - 1 • 717
3 = 18 - 1 • 15
-
           
Gelukt:   81 • 735 - 41 • 1452 = 3  dus a = -41  en b = 81  voldoen.
           
Stelling van Lamι
           
Een niet onbelangrijke vraag is:  "Hoe vaak moet je eigenlijk die blokjes eraf halen?" ofwel:  "Hoeveel stappen telt het Euclidisch algoritme?"
De stelling van Lamι zegt daarover:
           

Het aantal stappen dat nodig is in het Euclidisch algoritme
is hoogstens gelijk aan het aantal cijfers van het kleinste getal, vermenigvuldigd met 5.
           
In het voorbeeld van 1452 en 735 hierboven zou je maximaal 5 • 3 = 15 stappen nodig hebben (het waren er 4).

De volgende les zullen we een toepassing zien:  het oplossen van Diophantische vergelijkingen.
           

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