Обобщённый алгоритм Евклида

(Линейное представление наибольшего общего делителя).

Если d = НОД (a, b), то существуют такие целые числа x и y, что d = ax + by.

Пример.

1 = 7 x + 11 y

1 = 11 × 2 – 7 × 3

Теперь выведем общий метод вычисления линейного представления наибольшего общего делителя набора из произвольного количества чисел.

Определение

Линейным представлением числа d через набор чисел a₁, a₂, … , a_n называется выражение d = x₁a₁ + …. + x_na_n.

Теорема

d = НОД (a₁, … , a_n) Þ $ x₁, …. , x_n: d = x₁a₁ + …. + x_na_n.

Лемма

Элементарное преобразование a_i’ = a_i – ka_j не меняет линейную оболочку набора.

(Линейной оболочкой набора (a₁, … , a_n) называют множество всех выражений вида x₁a₁ + …. + x_na_n)

Доказательство леммы

Каждое число из линейной оболочки (a₁’, … , a_n’) входит в линейную оболочку (a₁, … , a_n), и наоборот.

На самом деле, если число представлено в виде t₁a₁’ + … + t_na_n’, то представив число a_i’ в виде a_i – ka_j, выразим все a₁’, … , a_n’ через (a₁, … , a_n) и получим коэффициенты разложения для системы (a₁, … , a_n).

Аналогично находим представление по системе (a₁’, … , a_n’), если известно разложение по системе (a₁, … , a_n).

Доказательство теоремы

Линейная оболочка набора (a₁, … , a_n) совпадает с линейной оболочкой (0, 0, …, d) (это следует из применения алгоритма Евклида).

Примеры.

276 = 84 × 3 + 24

84 = 24 × 3 + 12

24 = 12 × 2

Раскручивая последовательность вычислений в обратную сторону, получим:

24 = 276 – 84 × 3

12 = 84 – 24 × 3 = 84 – (276 – 84 × 3) × 3 = 84 × 10 – 276 × 3

Итак, 12 = 84 × 10 – 276 × 3

Общая формула:

a = bq₁ + r₁

b = r₁q₂ + r₂

r₁ = r₂q₃ + r₃

r₂ = r₃q₄ + r₄

…

r_k-2 = r_k-1q_k + r_k

r_k-1 = r_kq_k+1 + r_k+1

r_k = r_k+1q_k+2

Отсюда получаем:

r_k+1 = r_k-1 – r_kq_k+1

То есть мы выразили r_k+1 = НОД (a, b) через два предыдущих остатка: r_k и r_k-1.

Далее, воспользовавшись тем, что

r_k = r_k-2 – r_k-1q_k,

выразим r_k+1 в виде r_k+1 = r_k-1 – r_kq_k+1 = r_k-1 – (r_k-2 – r_k-1q_k)q_k+1. (1)

В этом случае получим линейное представление r_k+1 = НОД (a, b) через остатки r_k-1 и r_k-2.

Затем выразим r_k-1 через остатки r_k-2 и r_k-3, подставив полученное представление в формулу (1), получим представление НОД (a, b) через остатки r_k-2 и r_k-3. Продолжим процесс до тех пор, пока не получим линейное представление НОД (a, b) через a и b.