Есть два числа a,b. Для нахождения их Наибольшего Общего Делителя применяется алгоритма Евклида:
1) Простая версия: Пока числа не равны, из большего вычетаем меньшее. Результат - любое из чисел
2) Более быстрая версия: Пока оба числа одновременно не равны нулю, большее равняется остатку от деления его на меньшее