§ 2. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ И НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ

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

Целое число с называется общим делителем целых чисел если с есть делитель каждого из этих чисел.

ОПРЕДЕЛЕНИЕ. Наибольшим общим делителем целых чисел называется такой их общий делитель, который делится на любой общий делитель этих чисел. Целые числа называются взаимно простыми, если их наибольший общий делитель равен единице.

Наибольший общий делитель чисел обозначается НОД положительный наибольший общий делитель этих чисел обозначается

СЛЕДСТВИЕ 2.1. Если d есть наибольший обилий делитель целых чисел то множество всех общих делителей этих чисел совпадает с множеством всех делителей числа

СЛЕДСТВИЕ 2.2. Любые два наибольших общих делителя целых чисел ассоциированы, т. е. могут отличаться только знаком. Если d есть наибольший общий делитель чисел то число также есть наибольший общий делитель этих чисел.

ПРЕДЛОЖЕНИЕ 2.3. Если суть канонические разложения целых положительных чисел , то число

является наибольшим общим делителем чисел

Доказательство. Число d является делителем как числа а, так и числа b в силу предложения 1.7, т. е. d есть общий делитель а и b. Далее, если с — любой положительный общий делитель а и b, то в силу предложения 1.7

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

Поэтому Следовательно, d есть наибольший общий делитель чисел а и b.

Пусть — любые целые числа. Рассмотрим множество

всех целочисленных линейных комбинаций чисел . Легко проверить, что это множество есть идеал в . Этот идеал называется идеалом, порожденным числами и обозначается через

ТЕОРЕМА 2.4. Для любой совокупности целых чисел существует наибольший общий делитель. Число d является наибольшим общим делителем чисел тогда и только тогда, когда идеал равен идеалу

Доказательство. Если все числа равны нулю, то единственным наибольшим общим делителем этих чисел является число нуль.

Предположим, что хотя бы одно из чисел отлично от нуля. Рассмотрим множество всех целочисленных линейных комбинаций чисел . Множество содержит числа , так как , где для Поэтому множество I содержит числа, отличные от нуля. Множество I есть идеал кольца целых чисел, порожденный числами Согласно теореме 4.4, каждый идеал кольца является главным и, значит, состоит из кратных некоторого целого числа d, Докажем, что d есть НОД . Так как каждый элемент множества I делится на d, то для есть общий делитель чисел Далее, так как то ввиду (1) существуют такие целые числа что

Отсюда следует, что любой общий делитель с чисел есть также делитель числа d. Таким образом, любой элемент d, порождающий идеал является наибольшим общим делителем чисел Из доказанного, в частности, следует, что любая конечная совокупность чисел обладает наибольшим общим делителем.

Пусть — любой наибольший общий делитель чисел и d — по-прежнему число, порождающее идеал докажем, что . Любые два НОД чисел ассоциированы, т. е. могут отличаться только знаком. Ввиду этого . Поэтому идеал совпадает с идеалом (d). Следовательно,

Анализ доказательства предыдущей теоремы дает возможность формулировать также следующую теорему.

ТЕОРЕМА 2.5. Наибольший общий делитель d целых чисел представим в виде целочисленной линейной комбинации этих чисел, т. е. в форме с целыми При этом если не все числа равны нулю, то есть наименьшее целое положительное число, представимое в этой форме. Все числа, представимые в этой форт, т. е. все числа идеала являются кратными числу

ПРЕДЛОЖЕНИЕ 2.6. Если общий делитель d целых чисел представим в виде целочисленной линейной комбинации этих чисел, то d есть наибольший общий делитель чисел

Доказательство. Предположим, что общий делитель d чисел представим в виде

где — целые числа. Тогда любой общий делитель чисел делит сумму и, значит, d. Таким образом, d есть наибольший общий делитель чисел

ПРЕДЛОЖЕНИЕ 2.7. Для любых целых чисел а, b, с

Доказательство. Пусть есть . Тогда d есть общий делитель чисел и , а число есть общий делитель чисел Поэтому d есть общий делитель чисел а, b и с. Согласно теореме 2.5, числа d и можно представить в виде

где — целые числа; поэтому Таким образом, общий делитель d чисел а, b, с можно линейно выразить через эти числа. Следовательно, согласно предложению 2.6, d является наибольшим делителем этих чисел.

Это предложение дает возможность свести нахождение наибольшего общего делителя нескольких чисел к нахождению наибольшего общего делителя двух чисел.

ПРЕДЛОЖЕНИЕ 2.8. Для любых целых чисел а, b и с

Доказательство. Пусть d есть . Тогда согласно теореме 2.5 d можно представить в виде

где — целые числа, поэтому Кроме того, так как d есть общий делитель а и b, то есть общий делитель Следовательно, согласно предложению 2.6, число есть наибольший общий делитель чисел