Описание алгоритма нахождения НОД делением
1 - Большее число делим на меньшее.
2 - Если делится без остатка, то меньшее число и есть НОД.
3 - Если есть остаток, то большее число заменяем на остаток от деления.
4 - Переходим к пункту 1.
Пример такой:
Найти НОД для 30 и 18.
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6