Stosując ten sam sposób, ponownie zmniejszamy wartość większej liczby o wartość mniejszej: 867 – 255 = 612, nowa para liczb to: 255, 612
Pierwsza liczba, 255, jest wciąż mniejsza, ponownie więc odejmujemy 255 od liczby większej: 612 – 255 = 357, więc kolejna para liczb to: 255, 357
357 – 255 = 102, kolejna para to: 255, 102
Teraz widać, że 255 jest większą liczbą, odejmujemy więc od niej 102, co daje nam parę: 153, 102
Odjęcie 102 od 153 tworzy nam kolejną parę: 51, 102.
Teraz odejmujemy 51 od 102, co daje nam: 51, 51
Ponieważ obie liczby są sobie równe, kolejne odejmowanie da nam zero. Oznacza to, że największym wspólnym dzielnikiem liczb 1989 i 867 jest liczba 51.
Algorytm wykorzystujący funkcję modulo Algorytm wykorzystujący funkcję modulo to druga równoważna implementacja algorytmu Euklidesa. Poniżej przedstawiono wersję obliczania NWD liczb a i b wykorzystującą operację reszty z dzielenia (modulo): oblicz c jako resztę z dzielenia a przez b zastąp a liczbą b, następnie b liczbą c jeżeli wartość b wynosi 0, to a jest szukaną wartością NWD, w przeciwnym wypadku przejdź do kroku 1
Pseudokod
funkcja NWD(a, b) dopóki b ≠ 0 c := a mod b # reszta z dzielenia a przez b a := b b := c zwróć a