(Линейное представление наибольшего общего делителя).
Если d = НОД (a, b), то существуют такие целые числа x и y, что d = ax + by.
Пример.
1 = 7 x + 11 y
1 = 11 × 2 – 7 × 3
Теперь выведем общий метод вычисления линейного представления наибольшего общего делителя набора из произвольного количества чисел.
Определение
Линейным представлением числа d через набор чисел a1, a2, …, an называется выражение d = x1a1 + …. + xnan.
Теорема
d = НОД (a1, …, an) Þ $ x1, …., xn: d = x1a1 + …. + xnan.
Лемма
Элементарное преобразование ai’ = ai – kaj не меняет линейную оболочку набора.
(Линейной оболочкой набора (a1, …, an) называют множество всех выражений вида x1a1 + …. + xnan)
Доказательство леммы
Каждое число из линейной оболочки (a1’, …, an’) входит в линейную оболочку (a1, …, an), и наоборот.
На самом деле, если число представлено в виде t1a1’ + … + tnan’, то представив число ai’ в виде ai – kaj, выразим все a1’, …, an’ через (a1, …, an) и получим коэффициенты разложения для системы (a1, …, an).
Аналогично находим представление по системе (a1’, …, an’), если известно разложение по системе (a1, …, an).
|
|
Доказательство теоремы
Линейная оболочка набора (a1, …, an) совпадает с линейной оболочкой (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 = bq1 + r1
b = r1q2 + r2
r1 = r2q3 + r3
r2 = r3q4 + r4
…
rk-2 = rk-1qk + rk
rk-1 = rkqk+1 + rk+1
rk = rk+1qk+2
Отсюда получаем:
rk+1 = rk-1 – rkqk+1
То есть мы выразили rk+1 = НОД (a, b) через два предыдущих остатка: rk и rk-1.
Далее, воспользовавшись тем, что
rk = rk-2 – rk-1qk,
выразим rk+1 в виде rk+1 = rk-1 – rkqk+1 = rk-1 – (rk-2 – rk-1qk)qk+1. (1)
В этом случае получим линейное представление rk+1 = НОД (a, b) через остатки rk-1 и rk-2.
Затем выразим rk-1 через остатки rk-2 и rk-3, подставив полученное представление в формулу (1), получим представление НОД (a, b) через остатки rk-2 и rk-3. Продолжим процесс до тех пор, пока не получим линейное представление НОД (a, b) через a и b.