Алгоритм Евклида нахождения наибольшего общего делителя

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

а = q • b + r, где 0 £ r <b,

b=q₁•r+ r₁, где 0£r₁<r,

r =q₂•r₁+ r₂, где 0£r₂<r₁,

r₁ =q₃•r₂+ r₃, где 0£r₃<r₂,

…

r_k =q_k+2•r_k+1+ r_k+2, где 0£r_k+2<r_k+1,

…

r_п-1 =q_п+1•r_п.

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

(а, b) = (b, r) = (r, r₁) =... = (r_n-1, r_n) = r_n.

Поэтому наибольший делитель чисел а и b совпадает с r_n.

НОД двух чисел равен последнему отличному от нуля ос­татку в алгоритме Евклида.

Как следствие из алгоритма Евклида, можно получить утверждение, что наибольший делитель целых чисел а и b может быть представлен в виде линейной комбинации этих чисел, т. е. существуют целые числа и и v такие, что справедливо равенство

а • и + b • v = r_n.

Пример. Применим алгоритм Евклида к нахождению (175, 77).

(1) 175=77•2+21,

(2) 77=21•3+14,

(3) 21 =14 • 1 + 7,

(4) 14 = 7 • 2.

Последний положительный остаток – r₃ = 7. Значит, (175, 77) = 7.

Из предпоследнего соотношения (3) имеем

21 – 14 • 1 =7.

Подставляя сюда вместо 14 его представление из (2) получим

21 – (77 – 21•3) • 1 =7 или 21•4 – 77•1=7.

Подставляя сюда вместо 21 его представление из (1) получим

(175 – 77•2)•4 – 77•1=7 или 175•4 – 77•9=7.

Понятие наибольшего общего делители можно ввести и для нескольких чисел а₁,а₂,...,а_п. Его обозначают (а₁,а₂,...,а_п). Наибольший общий делитель нескольких чисел можно вычислить последовательно. Например, (а₁,а₂,а₃)= ((а₁,а₂),а_п), (а₁,а₂, а₃,а₄)= ((а₁,а₂, а₃),а₄) и т.д.