Grootste Gemene Deler

TERUGggd.html
Grootste Gemene Deler

Het algoritme van Euclides

Grootste Gemene Deler


Het algoritme van Euclides

Nog een extra voorbeeld: de ggd van de getallen 19.323 én 24.069:

Methode I


Stap  1 : 24069 - 19323 = 4746

Stap  2 : 19323 - 4746 = 14577

Stap  3 : 14577 - 4746 = 9831

Stap  4 : 9831 - 4746 = 5085

Stap  5 : 5085 - 4746 = 339

Stap  6 : 4746 - 339 = 4407

Stap  7 : 4407 - 339 = 3729

Stap  8 : 3729 - 339 = 3390

Stap  9 : 3390 - 339 = 3051

Stap10 : 3051 - 339 = 2721

Stap11 : 2721 - 339 = 2373

Stap12 : 2034 - 339 = 1695

Stap13 : 1695 - 339 = 1356

Stap14 : 1356 - 339 = 1017

Stap15 : 1017 - 339 = 617

Stap16 : 617 - 339 = 339

Stap17 : 339 - 339 = 0,


nul, dus de ggd van 24.069 en 19323 is gelijk aan 339, of ggd(24069,19232) = 339

Methode II


24069 = 1 ∙ 19323 + 4746

19323 = 4 ∙ 4746 + 339

4746 = 14 ∙ 339 + 0,


nul, dus de ggd van 24.069 en 19323 is gelijk aan 339, of ggd(24069,19232) = 339