Алгоритм Евклида

Алгоритм Евклида -- алгоритм, позволяющий быстро находить наибольший общий делитель двух натуральных чисел.

Алгоритм Евклида. Пусть даны натуральные числа a, b, и a>b. Через (a,b) обозначим НОД чисел a, b. Тогда (a,b) = (a-b,b).

Доказательство: Пусть d является общим делителем для a и b. Тогда a-b тоже делится на d. Получается, d является общим делителем для пары a-b, b. Обратно, пусть d -- общий делитель чисел a-b, b. Тогда a делится на d, т.к. a = (a-b)+b. Отсюда следует, что d также является общим делителем пары a, b. Значит множество общих делителей у пар a, b и a-b, b совпадают, а значит и наибольшие общие делители совпадают.

Улучшенный алгоритм Евклида. Пусть a = k*b+r, где k, r -- целые, и 0≤r<b (r -- остаток от деления a на b). Тогда (a,b) = (r,b).

Доказательство: Достаточно применить k раз шаг алгоритма Евклида. (a, b) = (a-b, b) = (a-2b, b) = ... = (a-k*b, b) = (r, b).

Пример: (1071, 462) = (147, 462) =(147, 21) = (0, 21) = 21.

Так как 1071 = 462*2+147, 462 = 147*3+21, 147 = 21*7+0.