Grootste Gemene Deler

TERUGHome.html
Grootste Gemene Deler

Het algoritme van Euclides

Grootste Gemene Deler


Het algoritme van Euclides

De algoritme van Euclides is de beste én snelste methode om de grootste gemene deler te vinden van twee positieve gehele getallen. De grootste gemene deler (ggd) van twee getallen is het grootste getal dat beide getallen zónder rest deelt. De ggd van getal a én getal b kun je schrijven als: ggd(a,b) = iets. Euclides van Alexandië (323 v.Chr. - 283 v.Chr.) beschreef deze methode (algoritme) in zijn boek „Elementen“ uit 300 v.Chr.

Het algoritme gaat er van uit dat de ggd van twee gehele getallen óók de ggd is van zowel het kleinste (van de eerste twee getallen) én het restgetal (bij deling van het grootste getal door het kleinste getal). Je kunt het ook anders zeggen (en het blijft hetzelfde), dat het ggd van twee getallen niet verandert als het kleinste getal van het grotere wordt afgetrokken.

Uitleg:


21 is de ggd van 252 (= 21 ∙ 12) én 105 (= 5 ∙ 12)


én


21 is ook de ggd van 147 (= 252 - 105 én = 7 ∙ 12) én 105 (= 5 ∙ 12)

Het algoritme van Euclides gaat volgens de onderstaande vier stappen:


  1. 1.1. noem het grootste van de beide getallen a, en het andere b;

  2. 2.2. trek b net zo vaal van a af totdat er 0 (= nul) over blijft óf een getal kleiner dan b;

  3. 3.3. wanneer er 0 over blijft zijn we klaar, en is b de ggd;

  4. 4.4. blijft er geen 0 over, herhaal dan het algortime met b als grootste getal én wat er over is van a als het kleinste getal. Met andere woorden begin weer bij stap 1.

Voorbeeld bij bovenstaande stappen van het algoritme van Euclides:


Wat is de ggd van 252 én 105?


Methode I:


Stap 1 : 252 - 105 = 147

Stap 2 : 147 - 105 =  42

Stap 3 : 105 -  42 =  63

Stap 4 :  63 -  42 =  21

Stap 5 :  42 -  21 =  21

Stap 6 :  21 -  21 =   0, nul dus is de ggd van 252 én 105 gelijk aan 21, óf ggd(252,105) = 21


Methode II:


Stap 1 : 252 = 2 ∙ 105 + 42

Stap 2 :  42 = 2 ∙  21 +  0, nul dus is de ggd van 252 én 105 gelijk aan 21, óf ggd(252,105) = 21


Zoals je ziet is methode I langer, maar simpeler; methode II is korter én iets (niet veel) ingewikkelder. Bij kleine getallen zit er bijna geen verschil tussen methode I en II. Als je met grotere getallen werkt kan methode II veel tijd besparen.


Nog een voorbeeld met 1160 én 800:


Methode I:


Stap 1 : 1160 - 800 = 360

Stap 2 :  800 - 360 = 440

Stap 3 :  440 - 360 =  80

Stap 4 :  360 -  80 = 280

Stap 5 :  280 -  80 = 200

Stap 6 :  200 -  80 = 120

Stap 7 :  120 -  80 =  40

Stap 8 :   80 -  40 =  40

Stap 9 :   40 -  40 =   0, nul dus is de ggd van 1160 én 800 gelijk aan 40, óf ggd(1160,800) = 40


Methode II:


Stap 1 : 1160 = 1 ∙ 800 + 360

Stap 2 :  800 = 2 ∙ 360 +  80

Stap 3 :  360 = 4 ∙  80 +  40

Stap 4 :   80 = 2 ∙  40 +   0, nul dus is de ggd van 1160 én 800 gelijk aan 40, óf ggd(1160,800) = 40

Het zal duidelijk zijn dat methode I onnodig lang duurt bij grotere getallen.


Het boek „elementen“ van Euclides, waar de algoritme in staat om de ggd te berekenen, komt uit 300 v.Chr. Het is de oudste algoritme die tegenwoordig nog gebruikt wordt in de moderne wiskunde. De originele algoritme werd alleen voor natuurlijke getallen beschreven. Echter in de 19de eeuw werd de algoritme veralgemeend tot andere soorten getallen. Een eeuw later, in de 20ste eeuw, werd de algoritme van Euclides nog verder veralgemeend naar andere wiskundige structuren; dan moet je denken aan knopen én multivariante veeltermen. In 1844 bewees Gabriel Lamé dat er nooit meer dan 5k stappen nodig zijn (als je het met methode II doet), om de ggd te vinden. De waarde van k staat voor het aanval cijfers van het getal; het getal 252 heeft 3 cijfers en k is dan 3: k = 3, dus maximaal 5k = 5 ∙ 3 = 15 stappen.

Toepassingen van de algoritme van Euclides


Er zijn veel toepassingen van dit algoritme; zowel theoretische en praktische. Het wordt gebruikt (in synthesizers) om bijna alle belangrijke muzikale ritmes te generen. Ook wordt dit algoritme gebruikt in de beveiliging van het internet; d.m.v. het zgn RSA algoritme. Bijvoorbeeld bij internetbankieren. Om Diophantische vergelijkingen op te lossen, ontkom je er niet aan het algoritme van Euclides. Als je met de Sturm-kettingmethode reële wortels van een veelterm wilt vinden óf kettingbreuken wilt construeren, denk je aan dit algoritme.