NWD liczb a i b możemy policzyć używając modulo.
Wystarczy, że będziemy powtarzać dwie operacje:

a = b
b = a modulo b

do momentu aż b będzie zero.
Wtedy w zmiennej a będzie wynik NWD