Приглашение в теорию чисел

ОРЕ О.

Пример. 1066 = 5 • 200 + 66; следовательно, (1066, 200) = (66, 200).

Этот результат, сформулированный в утверждении (4.3.3), дает нам простой метод вычисления наибольшего общего делителя двух чисел. Вместо поисков наибольшего общего делителя чисел а и b достаточно найти наибольший общий делитель чисел r и b. Эта задача более проста, так как число r меньше, чем каждое из чисел а и b. Чтобы найти наибольший общий делитель чисел r и b,

мы вновь воспользуемся тем же методом и разделим число b на r:

b = q₁r + r₁,

где r₁ меньше каждого из чисел b и r. В соответствии с правилом (4.3.3) мы получаем

d₀ = D(a, b) = D(b, r) = D(r, r₁).

Далее, таким же способом обращаемся с числами r и г₁ и т. д. В результате получаем последовательность пар чисел, каждая из которых имеет один и тот же наибольший общий делитель:

d₀ = D(a, b) = D(b, r) = D(r, r₁) = D(r₁, r₂) =… (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₀ = D(а, b) = r_k.

Другими словами, число d₀ равно первому из остатков, который делит предшествующий ему остаток.

Пример. Найдем наибольший общий делитель чисел 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), используя алгоритм Евклида.

2. Найдите наибольший общий делитель для каждой из пяти первых пар дружественных чисел. Сравните результаты с результатами, полученными с помощью разложения на простые множители.

3. Каким количеством нулей заканчивается число

n! = 1 • 2 • 3 •… • n?

Сверьте свой результат с таблицей факториалов.

§ 4. Наименьшее общее кратное

Вновь вернемся к дробям. Чтобы сложить (или вычесть) две дроби

c/a, d/b,

мы приводим их к общему знаменателю, а затем складываем (или вычитаем) числители.

Пример.

2/15 + 5/9 = 6/45 + 25/45 = 31/45.

Вообще, чтобы получить сумму

c/a + d/b,

мы должны найти общее кратное для чисел а и b, т. е. число m, на которое делятся как число а, так и b. Одно из таких чисел очевидно, а именно, их произведение m = ab; в результате получаем в качестве суммы дробей

c/a + d/b = cb/ab + da/ab = (cb + da)/ab.

Но существует бесконечно много других общих кратных для чисел а и b. Предположим, что мы знаем разложение этих двух чисел на простые множители:

а = р₁^α₁ • … • р_r^αr, b = р₁^β₁ •… • р_r^βr. (4.4.1)

Число m, которое делится одновременно на числа а и b, должно делиться на каждый простой делитель p_i чисел а и b и содержать его в степени μ_i не меньшей, чем большая из двух степеней α_i и β_i. Таким образом, среди общих кратных существует наименьшее