12.4 Algoritme van Euclides

Voor a > 0 en a een geheel getal is ggd(a,0)=a en als m geheel, 
dan geldt ggd(a,m)=ggd(m,a(mod m)).

Voorbeeld:
Bereken ggd(99, 45) met behulp van het algoritme van Euclides.
99 : 45 = 2 rest 9, want 99=2*45+9,
dus ggd(99, 45) = ggd(45, 9).
45 : 9 = 5 rest 0, want 45=5*9+0,
dus ggd(45, 9) = ggd(9,0) = 9 (want ggd(a, 0) = a).
Hieruit volgt dus ook ggd(99, 45) = 9.

Voor een berekening met kleine getallen kun je de berekening wel als hierboven opschrijven.
We zetten de tussenstappen in een tabel. We willen de 2 en de 9 uit de uitkomst 2 rest 9 graag in twee verschillende kolommen zetten. De 9 is de rest na deling. De rest geven we aan met de letter r. De 2 is het gehele deel van het quotiënt. Dit gehele deel geven we aan met de letter q.

 

a m q r
99 45 2 9
45 9 5 0
9 0  

 

Op elke regel is de ggd(a,m) gelijk, dus ggd(99,45)=ggd(45,9)=ggd(9,0)=9.

Voor het begruik van grotere getallen wordt een tabel onontbeerlijk.
Voorbeeld:
Bereken ggd(148104,47223).
Herhaald het algoritme van Euclides toepassen levert:

 

a m q r
148104 47223 3 6435
47223 6435 7 2178
6435 2178 2 2079
2178 2079 1 99
2079 99 21 0
99 0    

 

Opgave 8 

a) Waar vind je de grootste gemene deler in de bovenstaande tabel?
b) Wat is dus ggd(148104,47223)?

 

Opgave 9 

a) Bereken ggd(96, 22) met behulp van het algoritme van Euclides.
b) Bereken ggd(484, 576).
c) Bereken ggd(47957, 32395).