>0 =
d>1. Любой общий делитель чисел
а и
b также делит число
r = а — qb.
Следовательно, число r делится на d>0.
Так как число d>0 является делителем как числа r, так и числа b, то оно должно делить и число d>1 = D(b, r); отсюда d>1 ≥ d>0. С другой стороны, в соответствии с соотношением (4.3.1) любой общий делитель чисел r и b делит число а, откуда число d>1 делит число а. Так как число d>1 делит также и число b, то оно должно делить и число d>0 = D(a, b), следовательно, d>0 ≥ d>1. Из сказанного следует, что d>0 = d>1.
Пример. 1066 = 5 • 200 + 66; следовательно, (1066, 200) = (66, 200).
Этот результат, сформулированный в утверждении (4.3.3), дает нам простой метод вычисления наибольшего общего делителя двух чисел. Вместо поисков наибольшего общего делителя чисел а и b достаточно найти наибольший общий делитель чисел r и b. Эта задача более проста, так как число r меньше, чем каждое из чисел а и b. Чтобы найти наибольший общий делитель чисел r и b, мы вновь воспользуемся тем же методом и разделим число b на r:
b = q>1r + r>1,
где r>1 меньше каждого из чисел b и r. В соответствии с правилом (4.3.3) мы получаем
d>0 = D(a, b) = D(b, r) = D(r, r>1).
Далее, таким же способом обращаемся с числами r и г>1 и т. д. В результате получаем последовательность пар чисел, каждая из которых имеет один и тот же наибольший общий делитель:
d>0 = D(a, b) = D(b, r) = D(r, r>1) = D(r>1, r>2) =… (4.3.4)
Так как остатки постоянно уменьшаются, то эта последовательность должна закончиться после получения остатка r>k+1 = 0. Это происходит при делении
r>k-1 = q>k>+1r>k + 0,
т. е. число r>k делит число r>k-1. Тогда
D(r>k>-1, r>k) = r>k,
и из (4.3.4) видим, что
d>0 = D(а, b) = r>k.
Другими словами, число d>0 равно первому из остатков, который делит предшествующий ему остаток.
Пример. Найдем наибольший общий делитель чисел 1970 и 1066. Когда мы разделим одно число на другое и продолжим этот процесс дальше, как было выше рассказано, то найдем
1970 = 1 • 1066 + 904,
1066 = 1 • 904 + 162,
904 = 5 • 162 + 94,
162 = 1 • 94 + 68,
94 = 1 • 68 + 26,
68 = 2 • 26 + 16,
26 = 1 • 16+ 10,
16 = 1 • 10 + 6,
10 = 1 • 6 + 4,
6 = 1 • 4 + 2,
4 = 2 • 2 + 0.
Следовательно, (1970, 1066) = 2.
Этот метод нахождения наибольшего общего делителя двух чисел называется алгоритмом Евклида, так как первое его описание содержится в «Началах» Евклида. Этот метод очень удобен для применения в вычислительных машинах.
Система задач 4.3.
1. Решите задачу 1 § 1 (с. 49), используя алгоритм Евклида.
