Теорема 2.1.2.

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

2 . Rd(a*b)=Rd{ Rd (a) *Rd (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 = Q1.r + r1,

r = Q2.r1+ r2,

r = Q3.r2 + r3,

rn-1=Qn+1rn.

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

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

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

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

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