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

Пример. НОД (72, 96) = НОД (72, 96 - 72) = НОД (72, 24) = 24.

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

Приведём более строгое описание работы алгоритма.

Теорема

Множество общих делителей не меняется при элементарных преобразованиях набора (a₁, … a_n), то есть при замене a_i числом a_i - q× a_k.

В самом деле, если некоторое число d было общим делителем набора (a₁, … a_n), то все линейные комбинации этих чисел, в том числе a_i - q× a_k, делятся на d.

Аналогично, если число d₁ является общим делителем для набора, в котором провели замену, то оно является делителем q× a_k, а, следовательно, является делителем a_i. Следовательно, является делителем исходного набора.

Пример

276 = 84 × 3 + 24

84 = 24 × 3 + 12

24 = 12 × 2

НОД (276, 84) = НОД (84, 24) = НОД (12, 24) = НОД (12, 0) = 12

Общая формула алгоритма для двух чисел.

a = bq₁ + r₁

b = r₁q₂ + r₂

r₁ = r₂q₃ + r₃

r₂ = r₃q₄ + r₄

…

В конце концов остаток при делении окажется равен нулю, поскольку остатки уменьшаются с каждым шагом, и все они положительные.

r_k-1 = r_kq_k+1 + r_k+1

r_k = r_k+1q_k+2

Тогда НОД (a, b) = r_k+1 (то есть наибольший общий делитель равен последнему ненулевому остатку).

Алгоритм Евклида относится к так называемым «быстрым» алгоритмам, поскольку на каждом шаге остаток уменьшается по крайней мере в 2 раза, поэтому за сравнительно небольшое количество шагов алгоритм заканчивает работу.

Для трёх чисел вычисление наибольшего общего делителя может быть, например, таким.

НОД (65, 182, 130) = НОД (65, 182, 0) = НОД (65, 52, 0) = НОД (13, 0, 0) = 13.

Упражнения.

1. Найти НОД (111 111, 1111)

Решение:

Таким образом, НОД (111111, 1111) = 11.

2. Найти НОД (98, 147, 112)

Решение.

НОД (98, 147, 112) = НОД (98, 147, 14) = НОД (0, 147, 14) = НОД (0, 7, 14) = НОД (0, 7, 0) = 7