О. ОРЕ - Приглашение в теорию чисел

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

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

b = q 1 r + r 1,

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

d 0= D ( a, b ) = D ( b, r ) = D ( r, r 1).

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

d 0= D ( a, b ) = D ( b, r ) = D ( r, r 1) = D ( r 1, r 2) =… (4.3.4)

Так как остатки постоянно уменьшаются, то эта последовательность должна закончиться после получения остатка r k+1= 0. Это происходит при делении

r k-1= q k +1 r k + 0,

т. е. число r k делит число r k-1. Тогда

D ( r k -1, r k ) = r k ,

и из (4.3.4) видим, что

d 0= D ( а, b ) = r k .

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

Пример. Найдем наибольший общий делитель чисел 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 ?

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

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

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 , должно делиться на каждый простой делитель p i чисел а и b и содержать его в степени μ i не меньшей, чем б ольшая из двух степеней α i и β i . Таким образом, среди общих кратных существует наименьшее

m 0 = р 1 μ 1• … • р r μr , (4.4.2)

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

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

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

a = 2 2 5 1 • 7 1 • 11 0, b = 2 1 • 5 1 • 7 0 • 11 1,

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

К ( а, b ) = 2 25 1• 7 1• 11 1= 1540.

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

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

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

аb = p 1 α 1+β 1… • 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. Найдите наибольшее общее кратное для каждой из четырех первых пар дружественных чисел.

Во введении (§ 3, гл. 1) мы упоминали об одной из древнейших теоретико-числовых задач: найти все прямоугольные треугольники с целочисленными сторонами, т. е. найти все целочисленные решения уравнения

х 2+ y 2= z 2. (5.1.1)

Эта задача может быть решена с использованием лишь простейших свойств чисел. Прежде чем приступить к ее решению, проведем некоторые предварительные исследования. Тройка целых чисел

( х, у, z ), (5.1.2)

удовлетворяющая уравнению (5.1.1), называется пифагоровой тройкой . Отбросим тривиальный случай, когда одна из сторон треугольника равна нулю.

Ясно, что если множество (5.1.2) является пифагоровой тройкой, то любая тройка чисел

( kx, ky, kz ), (5.1.3)

получающаяся умножением каждого из этих чисел на некоторое целое число k , также будет пифагоровой, и наоборот. Таким образом, при поиске решений достаточно ограничиться нахождением простейших треугольников , длины сторон которых не имеют общего множителя k > 1. Например, тройки