Der Euklidische Algorithmus dient zur Bestimmung des ggT zweier (großer) Zahlen. Der Algorithmus läuft wie folgt ab:
Beispiel: ggT(48 548 ; 4293) = 53, denn: |
Dividend | Divisor | Rest | ||||
48 548 | = | 4 293 | · | 11 | + | 1 325 |
4 293 | = | 1 325 | · | 3 | + | 318 |
1 325 | = | 318 | · | 4 | + | 53 |
318 | = | 53 | · | 6 |
Kennen wir den ggT zweier Zahlen a und b (mit a < b), so erhalten wir das kgV nach folgender Rechnung: kgV = b · (a : ggT), kgV(48 548 ; 4 293) = 48 548 · (4 293 : 53) = 48 548 · 81 = 3 932 388. |