§ 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, поэтому оно делит и . Таким образом, взаимно делят друг друга и, следовательно, равны между собою.

2. Если делится на b, то с делится на b. Действительно (1, b), при делящемся на b, имеем и из 1 получаем . А этим (1, b) и доказывается делимость с на b.

3. Если каждое взаимно просто с каждым , то и произведение взаимно просто с произведением

Действительно, согласно 1 находим

и далее, полагая ради краткости точно таким же путем выводим