Алгоритм Евклида основан на том что отображение: (a, b) -> (a mod b, b) сохраняет HОД. Пример: (21, 15) 21 mod 15 = 6 15 mod 6 = 3 6 mod 3 = 0, соответсвенно НОД(21,15) = 3 (21, 8) 21 mod 8 = 5 8 mod 5 = 3 5 mod 3 = 2 3 mod 2 = 1, соответсвенно НОД(21,8) = 1
Двоичный алгоритм Евклида. основан на отображении: (a, b) -> ((a-b)/2, b), если а и b - нечетные -> (a/2, b) если a - четное, b - нечетное -> (a, b/2) если а - нечетное, b - четное