Het algoritme van Euclides

Met het algoritme van Euclides kan op een eenvoudige en zeer efficiënte manier de grootste gemene deler van twee getallen gevonden worden. De Griek Euclides gebruikte het algoritme al meer dan 2000 jaar geleden en formuleerde het in louter meetkundige termen. Die gedachtegang is het waard nog eens herhaald te worden. In een meetkundige redenering speelt het bestaan van een grootste gemene deler een fundamentele rol. Pas wanneer het probleem volledig getal-theoretisch wordt beschouwd vervalt die noodzak. Maar dat werd pas ver na Euclides duidelijk.

Delers en grootste gemene delers

Het doel van het algoritme van Euclides is het vinden van de grootste gemene deler van twee getallen. Een deler van een getal is een getal dat er precies een geheel aantal malen in past. Het getal n is dus een deler van het getal a wanneer er een geheel getal p is zodanig dat a = np. Van elk getal kunnen alle delers opgesomd worden. De delers van 6, bijvoorbeeld, zijn 1, 2, 3 en 6 en de delers van 9 zijn 1, 3 en 9. De grootste gemene deler van 6 en 9 is 3 omdat dit het grootste getal is dat in beide verzamelingen van delers voorkomt. De grootste gemene - in de betekenis van gemeenschappelijk - deler van twee getallen a en b is per definitie het grootste getal dat in beide verzamelingen van delers voorkomt. In het vervolg wordt dit aangeduid met ggd(a,b).

Wanneer a en b twee verschillende priemgetallen zijn, dan geldt ggd(a,b) = 1. Priemgetallen hebben maar twee delers, namelijk 1 en zichzelf, zodat bij twee verschillende priemgetallen alleen het getal 1 een gemeenschappelijke deler is. Wanneer ggd(a,b) = 1 betekent dat op zijn beurt nog niet dat a en b priemgetallen zijn. Immers, ggd(8,9) = 1 en zowel 8 als 9 zijn geen priemgetallen. Wanneer 1 de grootste gemene deler is, dan spreekt men van relatieve priemgetallen.

Meetkundige interpretatie

Euclides was een Griek - levend ongeveer 300 v.Chr. - en voor de oude Grieken was wiskunde vooral meetkunde. Euclides zelf heeft het algoritme dat nu zijn naam draagt, opgesteld met lijnstukken in zijn hoofd. De grootste gemene deler van twee getallen stond voor hem gelijk aan de lengte van duimstok waarmee twee lijnstukken van een gegeven lengte precies afgemeten kunnen worden. Dat ggd(6,9) = 3 betekende dus voor hem dat een duimstok met een lengte van 3 gebruikt kon worden om zowel de lijnstukken met lengtes 6 als 9 precies af te meten; zonder een stukje over te laten. De grootste gemene deler is de grootste duimstok die voor dat doel gebruikt kan worden.

Met dit beeld in het hoofd is het algoritme van Euclides eigenlijk heel eenvoudig. Neem allereerst twee lijnstukken van lengte a en b. Laat van deze twee b de langste zijn. Als a en b van gelijke lengte zijn dan kunnen ze beide als duimstok voor elkaar gebruikt worden en is de grootste gemene deler gewoon gelijk aan a of b.

Een cruciale aanname bij het opstellen van het algoritme is dat er een grootste gemene deler bestaat. Dat dit bepaald geen loze aanname is, wordt even verderop nog besproken. Het is de aanname dat er voor elk tweetal lijnen een duimstok bestaat waarmee ze beide exact gemeten kunnen worden.

De taak is dus het vinden van ggd(b,a). Hoewel niet strikt noodzakelijk, staan de argumenten van de ggd functie hier steeds in volgorde van grootte. Voor de formulering van het algoritme is dat wel zo handig. In de eerste stap van het algoritme wordt a, de kleinste van de twee, gebruikt als duimstok. Er zijn nu twee mogelijkheden. Of a past precies een geheel aantal malen in b of er blijft een restant over. In het eerste geval is a onze duimstok en geldt ggd(b,a) = a. In het tweede geval past a een aantal keren in b, zeg n keer, en laat een rest over. Het lijnstuk b wordt daarmee in twee delen opgedeeld: een stuk van lengte na en het restant, hier r genoemd, van r = b - na.

Nu komt de truc. Aangenomen wordt dus dat de grootste gemene deler van a en b bestaat. Deze kan aangeduid worden met g. Dan bestaan er gehele getallen p en q zodanig a = pg en b = qg. Immers, g past een geheel aantal malen in a en ook een geheel aantal malen in b. Na de eerste stap is het langste lijnstuk b in twee delen opgedeeld. Een deel waarin a, zo vaak als mogelijk is, is afgepast in b. Als dit n maal kan, dan is de lengte van dit stuk gelijk aan na. Het restant (r), heeft dus een lengte r = b-na. Omdat a = pg volgt na = npg zodat geconcludeerd mag worden dat na ook deelbaar is door g. Evenzo, omdat b=qg geldt ook dat r = qg - npg = (q-np)g en dit lijnstuk is dus ook deelbaar door g. De grootste gemene deler van a en b is dus ook de grootste gemene deler van na en b - na, oftewel ggd(b,a) = ggd(na,b-na) = ggd(na,r). Dit kan nog iets verder vereenvoudigd worden. Omdat het a is dat deelbaar moet zijn door g, mag de n hier weggelaten worden. Daarmee is gezegd dat: ggd(b,a) = ggd(a,r).

Uiteraard geldt dat na altijd groter is dan b - na en verder dat na kleiner is dan b. Door deze stap te zetten is het probleem vereenvoudigd omdat nu de ggd op basis van kleinere getallen gevonden kan worden. Als in deze tweede stap na geen veelvoud is van r, in welk geval r de grootste gemene deler is, dan kan de procedure weer herhaald worden. Het getal a mag vervangen worden door r en het getal b door na en dat mag, zoals hierboven uitgelegd, weer vervangen worden door a. Verder blijft alles hetzelfde. Deze procedure kan dus herhaald worden totdat op een gegeven moment de rest gelijk wordt aan 1 (een kleiner geheel getal is er immers niet). Dan moet in de laatste stap ggd(x,1) bepaald worden, waarin x het restant is dat in de voorlaatste stap bepaald is. En uiteraard geldt ggd(x,1) = x. Daarmee is de procedure compleet.

Voorbeeld

Neem a=243 en b=513. De te nemen stappen om ggd(513,243) te vinden staan hieronder uitgeschreven.

Stap 1: Vind ggd(513,243)

Het kleinste getal past twee keer in het grootste en laat en rest over van 27, want 513=2 x 243 + 27

Stap 2: Vind ggd(243, 27)

Het kleinste getal past 9 keer in het grootste, want 243=9 x 27 + 0

Stap 3: Vind ggd(27,0)

Hoewel deze stap eigenlijk overbodig is, valt hier onmiddellijk te lezen dat de grootste gemene deler gelijk is aan 27. (Omdat 0 door alles gedeeld kan worden).

De aanname dat er een grootste gemene deler bestaat

De aanname was dat de lengte van lijnen altijd gemeten kan worden met een (desnoods heel kleine) duimstok. Het was een grote schok voor de Griekse wiskunde toen men moest ontdekken dat er lijnstukken waren die niet met een duimstok gemeten konden worden. Hoe klein men de duimstok ook zou nemen, nooit kan het een geheel aantal malen op sommige lijnstukken afgepast worden. Zelfs nu nog, wanneer we tenminste getallen als lijnstukken zien, is deze verbijstering goed te snappen. Lijnstukken waarvan de lengte niet precies gemeten kunnen worden, moeten wel hele rare dingen zijn.

Maar met enkel een passer in de hand, het favoriete instrument van de Grieken bij het tekenen van lijnen (en cirkels), kan zo'n lijnstuk eenvoudig gemaakt worden. Men neme twee lijnstukken van gelijke lengte, zet ze loodrecht op elkaar (een eenvoudige constructie die met behulp van een passer goed uitgevoerd kan worden) en verbind vervolgens de open einden met een rechte lijn. Dan ontstaat er uiteraard een rechthoekige driehoek. Zonder verlies van algemeenheid mag de lengte van de twee lijnstukken die loodrecht op elkaar staan gelijk gesteld worden aan 1. De lengte van de andere lijn, hier aangeduid met c, volgt uit de stelling van Pythagoras en is uiteraard gelijk aan √2.

Maar er is geen duimstok waarmee de zijden van de driehoek met lengte 1 en tegelijk het lijnstuk c gemeten kan worden. Zou die er wel zijn, dan zou de lengte ervan een precies aantal malen in de lengte 1 moeten passen. De lengte van de duimstok mag dus gelijkgesteld worden aan 1/a, met a een (mogelijk heel groot) geheel getal. Een duimstok met lengte 1/a past uiteraard precies a maal in een lijnstuk van lengte 1. Welnu, dit duimstokje van lengt 1/a moet nu een geheel aantal malen passen op de lengte van lijnstuk c. Er moet dus een getal b bestaan zodanig dat b * (1/a) = b/a gelijk is aan de wortel uit 2. Maar, er bestaan helemaal geen gehele getallen a en b waarvoor dit geldt.

Dit was een schok voor de Grieken die zich ineens met een nieuw soort getallen geconfronteerd zagen. Een van de gevolgen ervan is dat het algoritme van Euclides in deze gevallen nooit zou stoppen. Steeds kan er een kleine duimstok gevonden worden, maar omdat er helemaal geen kleinste duimstok is, zal het algoritme tot in het oneindige doordraaien. De geschiedenis van de wiskunde leert dat zelfs wanneer dat het geval is het algoritme van Euclides nog zeer bruikbaar blijft. Maar daarover ging het hier niet. Hier hebben we ons beperkt tot paren van lijnstukken die wel met een en dezelfde duimstok te meten zijn.

Lees verder

• Hoeveel breuken zijn er?