Описание будет еще более точным, если мы формализуем процедуру соединения подмножеств, описанную выше.

Несколько простых примеров: НОД (10, 15) = 5; НОД (12, 16) = 4; НОД (13, 11) = 1; НОД (10, 20) = 10; НОД (17, 17) = 17.

Разложение на множители при поиске НОД (a, b) гораздо эффективнее, чем поиск делителей вплоть до меньшего из двух чисел a и b. Поиск простых множителей числа a потребует самое большее операций деления. Это значительное усовершенствование первоначального алгоритма, но в случае стозначных чисел даже наш новый метод становится уже чертовский сложной задачей.