Шрифт:
Система задач 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. Предположим, что мы знаем разложение этих двух чисел на простые множители:
а = р1α1 • … • рrαr, b = р1β1 •… • рrβr. (4.4.1)
Число m, которое делится одновременно на числа а и b, должно делиться на каждый простой делитель pi чисел а и b и содержать его в степени μi не меньшей, чем большая из двух степеней αi и βi. Таким образом, среди общих кратных существует наименьшее
m0 = р1μ1 • … • рrμr, (4.4.2)
в котором каждый показатель степени μi равен большему из чисел αi и βi. Очевидно, что число m0 является наименьшим общим кратным и любое другое общее кратное чисел а и b делится на m0. Для наименьшего общего кратного существует специальное обозначение
m0 = K(a, b). (4.4.3)
Пример. а = 140, b = 110. Разложение на простые множители этих чисел таково:
a = 22 51 • 71 • 110, b = 21 • 51 • 70 • 111,
следовательно,
К(а, b) = 22 51 • 71 • 111 = 1540.
Существует следующее простое соотношение между наибольшим общим делителем и наименьшим общим кратным:
ab = D(a, b) K(a,b). (4.4.4)
Доказательство. Перемножив два числа из (4.4.1), получим
аb = p1α1+β1 … • prαr+βr. (4.4.5)
Как мы отмечали, степень числа рi в D(a, b) является меньшей из двух чисел αi и βi, а в числе К(а, b) она большая из них. Предположим, что αi ≤ βi. Тогда степень числа рi в числе D(a, b) равна αi, а в К(а, b) равна βi; следовательно, в их произведении