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

Алгоритм Евклида применяется во многих задачах арифметики. Изучим вначале его применение для отыскания наибольшего общего делителя ненулевых целых чисел a, b. Рассмотрим теперь следующую процедуру деления целых чисел с остатком, которую и называют алгоритмом Евклида:

Шаг 0: a = bq₀ + r₀ (0 < r₀ < b)

Шаг 1: b = r₀q₁ + r₁ (0 < r₁ < r₀)

Шаг 2: r₀ = r₁q₂ + r₂ (0 < r₂ < r₁)

…

Шаг i: r_i–2 = r_i–1q_i + r_i (0 < r_i < r_i–1)

…

Шаг s: r_s–2 = r_s–1q_s + r_s (0 < r_s < r_s–1)

Шаг s +1: r_s–1 = r_sq_s+1 + 0 ( r_s+1 = 0 )

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

Если b | a, то r₀ = 0 и алгоритм завершается на шаге 0, т.к. (a, b) = b. В противном случае имеем: (a, b) = (bq₀ + r₀ , b) = (r₀ , b). Поэтому на шаге 1 делим с остатком b на r₀ . Если r₁ = 0, то (a, b) = (r₀ , b) = r₀ и алгоритм завершается. Если же r₁ > 0, то (a, b) = (r₀ , b) = (r₀ , r₀q₁ + r₁) = (r₀ , r₁). Поэтому на шаге 3 делим с остатком r₀ на r₁ , и.т.д. В результате получается убывающая последовательность остатков:

|b| > r₀ > r₁ > … > r_i > … > > r_s > … > 0 ,

которая не может убывать бесконечно. Значит, не более чем через |b| – 1 шаг – при некотором s – получится нулевой остаток, и

(a, b) = (b, r₀) = (r₀ , r₁) = … = (r_i , r_i+1) = … = (r_s–2 , r_s–1) = (r_s–1 , r_s) = r_s .

Значит, при r₀  0 последний делитель в алгоритме Евклида (или последний ненулевой остаток, если число шагов больше нуля) равен НОД(a, b). Таким образом, доказана следующая

Теорема (о нахождении НОД(a, b) с помощью алгоритма Евклида). Для любых ненулевых целых чисел a, b их наибольший общий делитель НОД(a, b) может быть найден с помощью алгоритма Евклида не более чем за min(|a|, |b|) – 1 шагов и равен последнему делителю в этом алгоритме (или последнему ненулевому остатку, если число шагов больше нуля).

Следствие 1 (о линейном разложении НОД(a, b)). Наибольший общий делитель НОД(a, b) любых ненулевых целых чисел a, b можно представить в виде линейной комбинации чисел a и b c целыми коэффициентами x и y: НОД(a, b) = ax + by. Такое представление называется линейным разложением наибольшего общего делителя чисел a и b.

Доказательство. Будем “ползти” сверху вниз по алгоритму Евклида. Если (a, b) = |b|, то алгоритм Евклида завершается на шаге 0, и существование линейного разложения очевидно: (a, b) = a0 + b(±1). Если же число шагов в алгоритме Евклида больше 0, будем последовательно представлять остатки r_i в виде r_i = ax_i + by_i (0  i  s). В результате x = x_s , y = y_s .

Ясно, что r₀ = a1 + b(–q₀), так что можно положить x₀ = 1, y₀ = –q₀ . Далее, r₁ = b1+r₀(–q₁) = b1+(a1+b(–q₀))(–q₁) = a(–q₁)+b(1+q₀q₁), т.е. x₁ = –q₁ , y₁ = 1+q₀q₁ . Предположим, что коэффициенты x_k , y_k построены для k = 0, 1, … , i–1 < s. Тогда шаг i алгоритма Евклида даёт равенство

r_i = r_i–2 + r_i–1(–q_i) = (ax_i–2 + by_i–2)+(ax_i–1 + by_i–1)(–q_i) =

= a(x_i–2 – x_i–1q_i)+b(y_i–2 – y_i–1q_i),

и можно положить x_i = x_i–2 – x_i–1q_i , y_i = y_i–2 – y_i–1q_i . Таким образом, доказано не только существование представлений r_i = ax_i + by_i (0  i  s), но и указан явный способ вычисления чисел x_k , y_k по следующим рекуррентным формулам :

(2  k  s).

Следствие 1 доказано.

Следствие 2 (о линейном разложении НОД(a₁ , … , а_n)). Наибольший общий делитель НОД(a₁ , … , a_n) любых ненулевых целых чисел a₁ , … , a_n можно представить в виде линейной комбинации этих чисел c целыми коэффициентами: НОД(a₁ , … , a_n) = a₁x₁+ …+a_nx_n . Такое равенство называется линейным разложением НОД(a₁ , … , a_n).

Доказательство. Воспользуемся доказанной выше формулой

(a₁ , … , a_n) = (((…((a₁ , a₂), a₃), … ), a_n–1), a_n).

Если D_n = (a₁ , … , a_n) и D_n–1 = (a₁ , … , a_n–1), то D_n = (D_n–1 , a_n). Линейное разложение для D₂ = (a₁ , a₂) уже построено. Если уже построены линейные разложения

D_n–1 = a₁u₁ + … + a_n–1u_n–1 , D_n = D_n–1u + a_nv,

то, подставив первое равенство во второе, получим

D_n = D_n–1u + a_nv = (a₁u₁ + … + a_n–1u_n–1)u + a_nv =

= a₁(u₁u) + … + a_n–1(u_n–1u) + a_nv –

линейное разложение НОД(a₁ , … , a_n).

Следствие 2 доказано.

Примеры: 1. Найти линейное разложение НОД(–6, 8, 34).

Имеем (–6, 8, 34) = ((–6, 8), 34) = (2, 34) = 2. При этом

(–6, 8) = 2 = (–6)(–3) + 8(–2), (2, 34) = 2 = 21 + 340,

(–6, 8, 34) = 2 = (2, 34) = 21 + 340 = ((–6)(–3) + 8(–2))1 + 340 =

= (–6)(–3) + 8(–2) + 340 –

линейное разложение НОД(–6, 8, 34).

2. Найти линейное разложение НОД(–12, 16, 34).

Аналогично предыдущему, (–12, 16, 34) = ((–12, 16), 34) = (4, 34) = 2,

(–12, 16) = 4 = (–12)(–3) + 16(–2), (4, 34) = 2 = 4(–8) + 341,

(–6, 8, 34) = 2 = (4, 34) = 4(–8) + 341 = ((–12)(–3) + 16(–2))1 + 341 =

= (–12)(–3) + 16(–2) + 341 –

линейное разложение НОД(–12, 16, 34).