Algorytm utworzymy w oparciu o tożsamość:
NWD (a1, a2,... , an) = NWD (NWD (a1, a2,... , an-1), an),
podaną w zadaniu drugim.
Za największy wspólny dzielnik obieramy liczbę a
1 , a następnie iteracyjnie obliczamy naj-
większy wspólny dzielnik zapamiętanego wyniku oraz liczby a
i dla kolejnych i = 2, 3, 4, ....,
n. Prowadzi to do następującego rozwiązania zadania:
w ← a1
dla i = 2, 3, 4, ...., n wykonuj
w ← NWD (w, ai)
zwróć w i zakończ
Podane rozwiązanie jest poprawne także wtedy, gdy n jest równe 1.