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

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. Таким образом, среди общих кратных существует наименьшее

m₀ = р₁^μ₁ • … • р_r^μr, (4.4.2)

в котором каждый показатель степени μ_i равен большему из чисел α_i и β_i. Очевидно, что число m₀ является наименьшим общим кратным и любое другое общее кратное чисел а и b делится на m₀. Для наименьшего общего кратного существует специальное обозначение

m₀ = K(a, b). (4.4.3)

Пример. а = 140, b = 110. Разложение на простые множители этих чисел таково:

a = 2²  5¹ • 7¹ • 11⁰, b = 2¹ • 5¹ • 7⁰ • 11¹,

следовательно,

К(а, b) = 2² 5¹ • 7¹ • 11¹ = 1540.

Существует следующее простое соотношение между наибольшим общим делителем и наименьшим общим кратным:

ab = D(a, b) K(a,b). (4.4.4)

Доказательство. Перемножив два числа из (4.4.1), получим

аb = p₁^α₁+β₁ … • p_r^α_r+β_r. (4.4.5)

Как мы отмечали, степень числа р_i в D(a, b) является меньшей из двух чисел α_i и β_i, а в числе К(а, b) она большая из них. Предположим, что α_i ≤ β_i. Тогда степень числа р_i в числе D(a, b) равна α_i, а в К(а, b) равна β_i; следовательно, в их произведении