Теорема 2.1.2

1. R_d(a+b)=R_d{ R_d (a) + R_d (b) }

2. R_d(a*b)=R_d{ R_d (a) *R_d (b) }

Доказательство предоставляется читателю в качестве упраж­нения.

Используя алгоритм деления, можно найти наибольший общий Делитель двух целых чисел. Например, НОД (814, 187) находится следующим образом:

814 = 4x187 +66,

187 = 2x66+55,

66 = 1x55 + 11,

55 = 5x11 +0.

Так как НОД (814, 187) делит и 814, и 187, то он должен делить и остаток 66. Так как он делит и 187, и 66, то он делит и 55. Так как он делит и 66, и 55, то он делит и 11. С другой стороны, 11 делит 55, а поэтому и 66, и 187, и, наконец, также 814. Следовательно, НОД (814, 187) равен 11.

Теперь можно выразить 11 в виде линейной комбинации чисел 814 и 187, начиная снизу выписанной выше последовательности и поступая следующим образом:

11 = 66 — 1 x 55 = 66 – 1x (187- 2x 66) =

= 3 x 66 — 1 x 187 = 3 x 814 — 13 x 187.

Следовательно, мы выразили НОД (814, 187) в виде линейной комбинации чисел 814 и 187 с коэффициентами из кольца целых чисел, а именно

НОД (814, 187) = 3 x 814 — 13 x 187. '.

Эти рассуждения могут быть проведены в общем виде для произвольных целых чисел r и s и позволяют доказать приведенные ниже теорему и следствие.

Теорема 2.1.3 (алгоритм Евклида). Наибольший общий де­литель двух различных ненулевых целых чисел r и s может быть вычислен итеративным применением алгоритма деления. Предпо­ложим, что r< s и оба эти числа положительны; тогда алгоритм состоит в следующем:

s = Q₁.r + r_1,

r = Q₂.r₁+ r₂,

r_\ = Q₃.r₂ + r₃,

r_n-1=Q_n+1r_n.

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

Наконец, мы приходим к важному и интуитивно не очевидному результату теории чисел.

Следствие 2.1.4. Для любых целых чисел г и s & существуют целые числа а и Ьb, такие, что

НОД ( r, s} = а r + bs.

Доказательство. Последний остаток в теореме 2.1.3 равен НОД ( r,s). Воспользуемся множеством выписанных в этой теореме уравнений, чтобы исключить все остальные остатки. Это даст выражение для г в виде линейной комбинации r и s с целочисленными коэффициентами.