Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
§ 2. Общий наибольший делитель
a. В дальнейшем мы будем рассматривать лишь положительные делители чисел. Всякое целое, делящее одновременно целые , называется их общим делителем. Наибольший из общих делителей называется общим наибольшим делителем и обозначается символом . Если , то называются взаимно простыми. Если каждое из чисел взаимно просто с каждым другим из них, то называются попарно простыми. Очевидно, числа попарно простые всегда и взаимно простые. В случае же двух чисел понятия «попарно простые» и «взаимно простые» совпадают.
Примеры. Числа 6, 10, 15, ввиду — взаимно простые. Числа 8, 13, 21, ввиду попарно простые.
b. Далее займемся общими делителями двух чисел.
1. Если а кратно b, то совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b; в частности
Действительно, всякий общий делитель чисел а и b является делителем и одного b. Обратно, раз а кратно b, то (1, b, § 1) всякий делитель числа b является также делителем числа а, т. е. является общим делителем чисел b и а. Таким образом, совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b. А так как наибольший делитель числа b есть само b, то
2. Если
то совокупность общих делителей чисел совпадает с совокупностью общих делителей чисел b и с; в частности .
Действительно, написанное равенство показывает, что всякий общий делитель чисел а и b делит также и с (2, b, § 1) и, следовательно, является общим делителем чисел b и с. Обратно, то же равенство показывает, что всякий общий делитель чисел бис делит а и, следовательно, является общим делителем чисел а и b. Таким образом, общие делители чисел а и b суть те же, что и общие делители чисел b и с; в частности, должны совпадать и наибольшие из этих делителей, т. е. (а, b).
c. Для разыскания общего наибольшего делителя, а также для вывода его важнейших свойств применяется алгоритм Евклида. Он состоит в нижеследующем. Пусть а и b — положительные целые и а Согласно с, § 1 находим ряд равенств
заканчивающийся, когда получается некоторое Последнее неизбежно, так как ряд как ряд убывающих целых не может содержать более чем b положительных.
d. Рассматривая равенства (1), идя сверху вниз, убеждаемся (b), что общие делители чисел а и b одинаковы с общими делителями чисел b и далее одинаковы с общими делителями чисел гг и чисел чисел наконец (а), с делителями одного числа являющегося последним не равным нулю остатком алгоритма Евклида. Одновременно с этим имеем
Мы приходим к следующим результатам.
1. Совокупность общих делителей чисел а и b совпадает с совокупностью делителей их общего наибольшего делителя.
2. Этот общий наибольший делитель равен последнему не равному нулю остатку алгоритма Евклида.
Пример. Применим алгоритм Евклида к отысканию (525, 231). Находим (вспомогательные вычисления приведены слева)
Здесь последний положительный остаток есть Значит,
1. Обозначая буквою любое положительное целое, имеем
2. Обозначая буквою любой общий делитель чисел а и b, имеем частности, имеем - честим от деления двух чисел на их общий наибольший делитель суть числа взаимно простые.
Действительно, умножив соотношения (1) почленно на , получим новые соотношения, где вместо а, b, будут стоять Поэтому и, таким образом, верно утверждение 1. Применяя утверждение 1, находим
Отсюда следует утверждение 2.
f. 1. Если то .
Действительно, делит значит, оно делит и ввиду равное с. Но делит и b, поэтому оно делит и . Обратно, делит и b, поэтому оно делит и . Таким образом, взаимно делят друг друга и, следовательно, равны между собою.