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

ОРЕ О.

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; следовательно, в их произведении

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

х² + y² = z². (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) не может быть простейшей тройкой. Такие же рассуждения применимы для доказательства остальных двух утверждений.