double arrow

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


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

Если 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.


Сейчас читают про: