Задача решается с помощью алгоритма Евклида. Этот алгоритм основывается на рекурентном соотношении НОД(a,b) = НОД(b,a mod b) при b > 0, НОД(a,b) = a при b = 0.