Wyznaczenie największego wspólnego dzielnika (NWD) liczb A i B

Istnieją różne algorytmy rozwiązujące niniejszy problem. Klasykę rozwiązań stanowi opisywany w większości książek algorytm Euklidesa wykorzystujący kolejne dzielenie całkowite ( dzielenie z resztą ) liczb.

Przedstawiony algorytm jest modyfikacją klasycznego algorytmu Euklidesa. Polega na szukaniu różnicy dwóch liczb (gdy są różne). W kolejnym etapie większa liczba zostaje odrzucona i rozpatrywane są uzyskana różnica i mniejsza liczba. Gdy uzyskana zostanie równość to jako NWD przyjęta zostaje jedna z ostatecznie porównywanych liczb. Np. NWD (18, 30) = 6, gdyż:
18 - 12 = 6
12 - 6 = 6
6 = 6