О. ОРЕ - Приглашение в теорию чисел
а = р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; следовательно, в их произведении
D(a, b) К(а, b)
она равна αi + βi, что в точности равняется степени в произведении (4.4.5). Это показывает справедливость соотношения (4.4.4).
Пример. а = 140, b = 110, D(a, b) = 10, К(а, b) = 1540.
ab = 140 • 110 = 10 • 1540 = D(a, b) К(а, b).
Из правила (4.4.4) вытекает, что если а и b взаимно простые, то их произведение равно их наибольшему общему кратному; действительно, в этом случае D(a, b) = 1 и поэтому ab = K(а, b).
Система задач 4.4.
1. Найдите наибольшее общее кратное пар чисел в системе задач 4.1 (с. 49).
2. Найдите наибольшее общее кратное для каждой из четырех первых пар дружественных чисел.
ГЛАВА 5
ЗАДАЧА ПИФАГОРА
§ 1. Предварительные замечания
Во введении (§ 3, гл. 1) мы упоминали об одной из древнейших теоретико-числовых задач: найти все прямоугольные треугольники с целочисленными сторонами, т. е. найти все целочисленные решения уравнения
х2 + y2 = z2. (5.1.1)
Эта задача может быть решена с использованием лишь простейших свойств чисел. Прежде чем приступить к ее решению, проведем некоторые предварительные исследования. Тройка целых чисел
(х, у, z), (5.1.2)
удовлетворяющая уравнению (5.1.1), называется пифагоровой тройкой. Отбросим тривиальный случай, когда одна из сторон треугольника равна нулю.
Ясно, что если множество (5.1.2) является пифагоровой тройкой, то любая тройка чисел
(kx, ky, kz), (5.1.3)
получающаяся умножением каждого из этих чисел на некоторое целое число k, также будет пифагоровой, и наоборот. Таким образом, при поиске решений достаточно ограничиться нахождением простейших треугольников, длины сторон которых не имеют общего множителя k > 1. Например, тройки
(6, 8, 10), (15, 20, 25)
являются пифагоровыми тройками, получающимися из простейшего решения (3, 4, 5).
В простейшей тройке (x, у, z) не существует общего множителя для всех трех чисел. В действительности справедливо более сильное утверждение: никакие два числа из простейшей тройки не имеют общего множителя, т. е.
D(x, y) = 1, D(x, z) = 1, D(y, z) = 1. (5.1.4)
Чтобы доказать это, предположим, что, например, х и у имеют общий делитель. Тогда они имеют общий простой делитель р. В соответствии с (5.1.1) число р должно также делить и r. Итак, (х, у, z) не может быть простейшей тройкой. Такие же рассуждения применимы для доказательства остальных двух утверждений.
Рассмотрим еще ряд свойств простейших троек. Мы только что получили, что числа х и у не могут быть оба четными, но мы можем также показать, что они не могут быть и оба нечетными. Действительно, предположим, что
x = 2a +1, y = 2b + 1.
После возведения в квадрат этих чисел и сложения их, получим число
x2 + y2 = (2a + 1)2 + (2b + 1)2 = 2 + 4а + 4a2 + 4b + 4b2 = 2 + 4 (а + а2 + b + b2),
делящееся на 2, но не делящееся на 4. В соответствии с (5.1.1) это означает, что z2 делится на 2, но не делится на 4, но это невозможно, так как если z2 делится на 2, то и z делится на 2, но тогда z2 делится на 4.
Так как одно из чисел х и у — четное, а другое — нечетное, то z — также нечетное. Для определенности будем считать, что в наших обозначениях число х — четное, а у — нечетное.
§ 2. Решение задачи Пифагора
Чтобы найти простейшие решения уравнения Пифагора (5.1.1), перепишем его в виде
x2 = z2 — y2 = (z + y)(z — y). (5.2.1)
Вспоминая, что х — четное, а у и z — оба нечетные, получаем, что все три числа
х, z + y, z — y
четные. Тогда мы можем разделить обе части уравнения (5.2.1) на 4 и получить
(1/2 x)2 = 1/2 (z + y) 1/2 (z — y). (5.2.2)
Обозначим
m1 = 1/2 (z + y), n1 = 1/2 (z — y); (5.2.3)
тогда уравнение (5.2.2) перепишется как
(1/2 x)2 = m1n1. (5.2.4)
Числа m1 и n1 взаимно простые. Чтобы это увидеть, предположим, что
d = D(m1, n1)
есть наибольший общий делитель чисел m1 и n1. Тогда, как это следует из § 1 гл. 4, число d должно делить оба числа
m1 + n1 = z, m1 — n1 = y.
Но единственным общим делителем чисел z и у в простейшей тройке может быть только 1, поэтому
d = D(m1, n1) = 1. (5.2.5)
Так как произведение (5.2.4) этих двух взаимно простых чисел является квадратом, то можно использовать результат, изложенный в конце § 2 гл. 4 (стр. 50), согласно которому числа m1 и n1 являются квадратами
m1 = m2, n1 =, D(m, n) = 1. (5.2.6)
Здесь мы можем без нарушения общности считать, что m > 0, n > 0. Теперь подставим m2 и n2 вместо m1 и n1 соответственно в уравнения (5.2.3) и (5.2.4);
получим
m2 = 1/2 z + 1/2 y, n2 = 1/2 z — 1/2 y, m2n2 = 1/4 x2,
т. е.
x = 2mn, y = m2 — n2, z = m2 + n2. (5.2.7)
