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

§ 1. Наибольший общий делитель

Откровенно говоря, мы надеемся, что многое в этой главе окажется для вас знакомым.

В ней рассматриваются понятия, с которыми вы познакомились в школе, как только научились обращаться с обыкновенными дробями. Единственным оправданием включения этого материала является желание освежить его в вашей памяти. Мы также надеемся, что приведенное изложение материала явится более систематическим, чем то, к которому вы привыкли.

Возьмем некоторую дробь а/b, отношение двух целых положительных чисел а и b. Обычно мы стараемся привести ее к простейшему виду, т. е. мы стараемся сократить множители, общие для а и b.

Эта операция не изменяет значения дроби, например,

24/36 = 8/12 = 2/3.

Общим делителем двух натуральных чисел а и b называется натуральное число d, которое является множителем как числа а, так и числа b, т. е.

a = d • а₁, b = d • b₁.

Если число d — общий делитель чисел а и b, то он также делит числа а + b и а — b, так как

а + b = а₁d + b₁d = (а₁ + b₁) d,

а — b = а₁d — b₁d = (а₁ — b₁) d.

Когда известны разложения чисел а и b на простые множители, нетрудно найти все их общие делители. Выпишем эти два разложения на простые множители:

а = р₁^α₁ • … • р_r^α_r, b = р₁^β₁ • … • р_r^β_r. (4.1.1)

Здесь мы договариваемся записывать разложения чисел а и b так, как если бы они имели одинаковые простые множители

р₁, p₂…, р_r

но с условием, что мы допускаем возможность использования показателя степени, равного 0. Например, если p₁ делит число а, но не делит число b, мы полагаем, что в формуле (4.1.1) β₁ = 0. Таким образом, если

а = 140, b = 110, (4.1.2)

то

а = 2² • 5¹ • 7¹ • 11⁰, b = 2¹ • 5¹ • 7⁰ • 11¹. (4.1.3)

Из формулы (4.1.1) следует, что любой делитель d числа а может иметь простыми множителями только числа p_i, которые встречаются в числе а и каждое из них содержится в степени δ_i, не превосходящей соответствующей степени α_i в числе а. Аналогичные условия имеют место и для любого делителя d числа b. Поэтому общий делитель d чисел а и b может иметь в качестве простых множителей только числа p_i, которые встречаются одновременно в числах а и b, а степень δ_i числа p_i в d не может превосходить меньшей из двух степеней: α_i и β_i.

Из этого обсуждения мы можем сделать вывод: любые два натуральных числа а и b имеют наибольший общий делитель d₀. Простыми множителями p_i числа d₀ являются те, которые одновременно встречаются в числах а и b, а степень числа р_i в числе d₀ есть меньшее из двух чисел α_i и β_i.

Пример. Возьмем два числа, указанных в (4.1.2), имеющие разложения на простые множители (4.1.3); очевидно, что

d₀ = 2¹ 5¹ = 10.

Так как степень простого числа p_i в наибольшем общем делителе по крайней мере не меньше, чем у любого другого общего делителя, то мы получаем характеристическое свойство:

Любой общий делитель d делит наибольший общий делитель d₀.

Наибольший общий делитель двух чисел настолько важен, что для него существует специальное обозначение:

d₀ = D(a, b). (4.1.4)

Система задач 4.1.

1. Найдите наибольший общий делитель пар чисел: а) 360 и 1970, б) 30 и 365, в) номера вашего телефона и вашего почтового индекса.

2. Как бы вы стали доказывать, что √2 есть иррациональное число, используя в доказательстве теорему о единственности разложения?

§ 2. Взаимно простые числа

Число 1 является общим делителем для любой пары чисел а и b. Может случиться, что единица будет единственным их общим делителем, т. е.

d₀ = D(a, b) = 1. (4.2.1)

В этом случае мы говорим, что числа а и b взаимно простые.

Пример. (39, 22) = 1.

Если числа имеют общий делитель, больший единицы, то они также имеют общий простой делитель.

Итак, два числа могут быть взаимно простыми только тогда, когда они не имеют общих простых множителей, поэтому условие (4.2.1) означает, что числа а и b не имеют общих простых множителей, т. е. все их простые множители различны.

Вернемся к началу этой главы, где мы приводили дробь а/b к простейшему виду. Если d₀ есть наибольший общий делитель чисел а и b, то мы можем написать

a = a₀d₀, b = b₀d₀. (4.2.2)

Тогда

a/b = a₀d₀/b₀d₀ = a₀/b₀. (4.2.3)

В формуле (4.2.2) числа а₀ и b₀ не могут иметь простых общих множителей, в противном случае числа а и b имели бы общин множитель, больший, чём d₀. Следовательно,

D(a₀, b₀) = 1. (4.2.4)

Это означает, что для второй дроби в формуле (4.2.3) дальнейшее сокращение невозможно.

Одним из часто применяемых свойств взаимно простых чисел является следующее.

Если произведение ab делится на число с, которое взаимно просто с числом b, то число а делится на с.

Доказательство. Так как число с делит произведение ab, то простые множители числа с содержатся среди простых множителей чисел а и b. Но так как D(b, c) = 1, то их не может быть среди множителей числа b. Таким образом, все простые множители числа с делят число а, но не делят число b, и они появляются в числе а в степенях, не меньших, чем в числе с, так как число с делит ab.

Позже мы используем другой факт.

Если произведение двух взаимно простых чисел является квадратом,

ab = c², D(a, b) = 1, (4.2.5)

то числа а и b являются квадратами:

а = а₁², b = b₁². (4.2.6)

Доказательство. Для того чтобы некоторое число было квадратом, необходимо и достаточно, чтобы все степени в разложении его на простые множители были четными. Так как числа а и b — взаимно простые (4.2.5), то любой простой множитель из с² содержится либо в а, либо в b, но не в обоих; отсюда простые множители чисел а и b должны иметь четные степени.

Система задач 4.2.

1. Какие числа взаимно простые с числом 2?

2. Почему D(n, n + 1) = 1?

3. Исследуйте пары дружественных чисел в табл. 2 (стр. 45) и найдите те из них, которые взаимно просты.

4. Может ли правило, выраженное в формулах (4.2.5) и (4.2.6), быть справедливым не только для квадратов, но и для произвольных степеней?

§ 3. Алгоритм Евклида

Вновь вернемся к нашим дробям а/b. Если а > b, то дробь является числом, большим 1, и мы часто разделяем ее на целую часть и правильную дробь, меньшую единицы.

Примеры. Мы пишем

32/5 = 6 + 2/5 = 6 2/5, 63/7 = 9 + 0/7 = 9.

В общем случае мы используем деление с остатком

чисел а и b (a ≥ b), а именно:

a = qb + r, где 0 ≤ r ≤ b—1. (4.3.1)

Рис. 14.

Очевидно, что это всегда возможно. Действительно, рассмотрим числа 0, 1, 2… на числовой прямой (рис. 14). Где-то на этой прямой расположено число а. Начиная от точки 0 станем отмечать точки b, 2b, Зb и т. д. до точки qb такой, что qb не больше, чем а, в то время как (q + 1)b уже больше а. Расстояние от точки qb до точки а и есть r. Мы называем число r остатком при делении (4.3.1), a q — частным. Это частное q встречается столь часто, что имеется специальный символ для его обозначения:

q = [a/b].

Этот символ обозначает наибольшее целое число, не превосходящее числа а/b. Для примеров, приведенных выше, получим

[32/5] = 6, [63/7] = 9.

В предыдущем разделе мы исследовали наибольший общий делитель двух натуральных чисел а и b:

d₀ = D(a, b). (4.3.2)

Чтобы найти число d₀, мы полагали, что мы знаем разложения чисел а и b на простые множители. Однако нахождение таких разложений может оказаться очень трудным занятием для больших чисел. Существует совсем другой метод для нахождения наибольшего общего делителя, который не использует подобных разложений. Он основан на следующем:

Если a = qb + r, где 0 ≤ r ≤ b—1, то

D(a, b) = d = D(r, b). (4.3.3)

Доказательство. Запишем

d₀ = D(a, b), d₁ = D(r, b).

Таким образом, доказательство соотношения (4.3.3) означает доказательство того, что d₀ = d₁. Любой общий делитель чисел а и b также делит число

r = а — qb.

Следовательно, число r делится на d₀.

Так как число d₀ является делителем как числа r, так и числа b, то оно должно делить и число d₁ = D(b, r); отсюда d₁ ≥ d₀. С другой стороны, в соответствии с соотношением (4.3.1) любой общий делитель чисел r и b делит число а, откуда число d₁ делит число а. Так как число d₁ делит также и число b, то оно должно делить и число d₀ = D(a, b), следовательно, d₀ ≥ d₁. Из сказанного следует, что d₀ = d₁.

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

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

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

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. Найдите наибольшее общее кратное для каждой из четырех первых пар дружественных чисел.