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

В дальнейшем мы будем рассматривать лишь положительные делители чисел. Всякое целое, делящее одновременно целые a, b, …, l, называется их общим делителем. Наибольший из общих делителей называется наибольшим общим делителем и обозначается символом (a, b, …, l).

Пример: Числа 6, 10, 15, ввиду (6, 10, 15) = 1, - взаимно простые. Числа 8, 13, 21, ввиду (8, 13) = (8, 21) = (13, 21) = 1, - попарно простые.

Далее займемся общими делителями двух чисел.

Теорема 1: Если а кратно b, то совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b; в частности (а, b) = b.

Доказательство: Всякий общий делитель чисел а и b является делителем и одного b. Обратно, раз а кратно b, то (п. 1, Теорема 1) всякий делитель числа b является также делителем числа а, т. е. является общим делителем чисел b и а. Таким образом, совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b. А так как наибольший делитель числа b есть само b, то (a, b) = b.

Теорема 2: Если

a = bq + c,

то совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и с; в частности (а, b) = (b, с).

Доказательство: Написанное равенство показывает, что всякий общий делитель чисел а и b делит также и с (п. 1, Теорема 2) и, следовательно, является общим делителем чисел b и с. Обратно, то же равенство показывает, что всякий общий делитель чисел b и с делит а и, следовательно, является общим делителем чисел а и b. Таким образом, общие делители чисел а и b суть те же, что и общие делители чисел b и с; в частности, должны совпадать и наибольшие из этих делителей, т.

Для разыскания общего наибольшего делителя, а также для вывода его важнейших свойств, применяется алгоритм Евклида. Он состоит в нижеследующем. Пусть а и b - положительные целые и а > b. Согласно (п. 1, Теорема 3) находим ряд равенств

a = bq₁ + r₂, 0 < r₂ < b,

b = r₂q₂ + r₃, 0 < r₃ < r₂,

r₂ = r₃q₃ + r₄, 0 < r₄ < r₃,

… (1)

r_n-2 = r_n-1q_n-1 + r_n, 0 < r_n < r_n-1,

r_n-1 = r_nq_n,

заканчивающийся, когда получается некоторое r_n+1 = 0. Последнее неизбежно, так как ряд b, r₂, r₃, ... как ряд убывающих целых не может содержать более чем b положительных.

Рассматривая равенства (1), идя сверху вниз, убеждаемся, что общие делители чисел а и b одинаковы с общими делителями чисел b и r₂, далее одинаковы с общими делителями чисел r₂ и r₃, чисел r₃ и r₄, ..., чисел r_n-1 и r_n, наконец, с делителями одного числа r_n, являющегося последним не равным нулю остатком алгоритма Евклида. Одновременно с этим имеем

(а, b) = (b, r₂) = (r₂, r₃) = ... = (r_n-1, r_n) = r_n.

Мы приходим к следующим результатам.

Теорема 3: Совокупность общих делителей чисел а и b совпадает с совокупностью делителей их наибольшего общего делителя.

Теорема 4: Этот наибольший общий делитель равен последнему не равному нулю остатку алгоритма Евклида.

Пример: Применим алгоритм Евклида к отысканию (525, 231). Находим (вспомогательные вычисления приведены слева)

Здесь последний положительный остаток есть r₄ = 21.

Теорема 5: Обозначая буквою m любое положительное целое, имеем (am, bm) = (a, b)m.

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

Доказательство: Умножив соотношения (1) почленно на т, получим новые соотношения, где вместо a, b, r₁, …, r_n будут стоять am, bm, r₁m, …, r_nm. Поэтому (am, bm) = r_nm и, таким образом, верно утверждение теоремы 5.

Применяя утверждение теоремы 5, находим

.

Отсюда следует утверждение теоремы 6.

Теорема 7: Если (а, b) = 1, то (ас, b) = (с, b).

Доказательство: (ас, b) делит ас и bc, значит, (Теорема 3) оно делит и (ас, bc) (Теорема 5) равное с. Но (ас, b) делит и b, поэтому оно делит и (с, b). Обратно, (с, b) делит ас и b, поэтому оно делит и (ас, b). Таким образом, (ас, b) и (с, b) взаимно делят друг друга и, следовательно, равны между собою.

Теорема 8: Если (a, b) = 1 и ас делится на b, то с делится на b.

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

Теорема 9: Если каждое а₁, a₂, ..., а_m взаимно просто с каждым b₁, b₂, ..., b_n, то и произведение а₁a₂…а_m взаимно просто с произведением b₁b₂…b_n.

Доказательство: Согласно (Теоремы 7) находим

(a₁a₂a₃…a_m, b_k) = (a₂a₃…a_m, b_k) = (a₃…a_m, b_k) = … = (a_m, b_k) = 1,

и далее, полагая ради краткости a₁a₂a₃…a_m = А, точно таким же путем выводим

(b₁b₂b₃…b_n, A) = (b₂b₃…b_n, A) = (b₃…b_n, A) = … = (b_n, A) = 1. 3