но с условием, что мы допускаем возможность использования показателя степени, равного 0. Например, если p1 делит число а, но не делит число b, мы полагаем, что в формуле (4.1.1) β1 = 0. Таким образом, если
а = 140, b = 110, (4.1.2)
то
а = 22 • 51 • 71 • 110, b = 21 • 51 • 70 • 111. (4.1.3)
Из формулы (4.1.1) следует, что любой делитель d числа а может иметь простыми множителями только числа pi, которые встречаются в числе а и каждое из них содержится в степени δi, не превосходящей соответствующей степени αi в числе а. Аналогичные условия имеют место и для любого делителя d числа b. Поэтому общий делитель d чисел а и b может иметь в качестве простых множителей только числа pi, которые встречаются одновременно в числах а и b, а степень δi числа pi в d не может превосходить меньшей из двух степеней: αi и βi.
Из этого обсуждения мы можем сделать вывод: любые два натуральных числа а и b имеют наибольший общий делитель d0. Простыми множителями pi числа d0 являются те, которые одновременно встречаются в числах а и b, а степень числа рi в числе d0 есть меньшее из двух чисел αi и βi.
Пример. Возьмем два числа, указанных в (4.1.2), имеющие разложения на простые множители (4.1.3); очевидно, что
d0 = 21 51 = 10.
Так как степень простого числа pi в наибольшем общем делителе по крайней мере не меньше, чем у любого другого общего делителя, то мы получаем характеристическое свойство:
Любой общий делитель d делит наибольший общий делитель d0.
Наибольший общий делитель двух чисел настолько важен, что для него существует специальное обозначение:
d0 = D(a, b). (4.1.4)
Система задач 4.1.
1. Найдите наибольший общий делитель пар чисел: а) 360 и 1970, б) 30 и 365, в) номера вашего телефона и вашего почтового индекса.
2. Как бы вы стали доказывать, что √2 есть иррациональное число, используя в доказательстве теорему о единственности разложения?
§ 2. Взаимно простые числа
Число 1 является общим делителем для любой пары чисел а и b. Может случиться, что единица будет единственным их общим делителем, т. е.
d0 = D(a, b) = 1. (4.2.1)
В этом случае мы говорим, что числа а и b взаимно простые.
Пример. (39, 22) = 1.
Если числа имеют общий делитель, больший единицы, то они также имеют общий простой делитель.
Итак, два числа могут быть взаимно простыми только тогда, когда они не имеют общих простых множителей, поэтому условие (4.2.1) означает, что числа а и b не имеют общих простых множителей, т. е. все их простые множители различны.
Вернемся к началу этой главы, где мы приводили дробь а/b к простейшему виду. Если d0 есть наибольший общий делитель чисел а и b, то мы можем написать
a = a0d0, b = b0d0. (4.2.2)
Тогда
a/b = a0d0/b0d0 = a0/b0. (4.2.3)
В формуле (4.2.2) числа а0 и b0 не могут иметь простых общих множителей, в противном случае числа а и b имели бы общин множитель, больший, чём d0. Следовательно,
D(a0, b0) = 1. (4.2.4)
Это означает, что для второй дроби в формуле (4.2.3) дальнейшее сокращение невозможно.
Одним из часто применяемых свойств взаимно простых чисел является следующее.
Если произведение ab делится на число с, которое взаимно просто с числом b, то число а делится на с.
Доказательство. Так как число с делит произведение ab, то простые множители числа с содержатся среди простых множителей чисел а и b. Но так как D(b, c) = 1, то их не может быть среди множителей числа b. Таким образом, все простые множители числа с делят число а, но не делят число b, и они появляются в числе а в степенях, не меньших, чем в числе с, так как число с делит ab.
Позже мы используем другой факт.
Если произведение двух взаимно простых чисел является квадратом,
ab = c2, D(a, b) = 1, (4.2.5)
то числа а и b являются квадратами:
а = а12, b = b12. (4.2.6)
Доказательство. Для того чтобы некоторое число было квадратом, необходимо и достаточно, чтобы все степени в разложении его на простые множители были четными. Так как числа а и b — взаимно простые (4.2.5), то любой простой множитель из с2 содержится либо в а, либо в 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, и мы часто разделяем ее на целую часть и правильную дробь, меньшую единицы.