## 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).