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

Определение 3.1. Рассмотрим целых чисел и целое число , причем . Число называется общим делителем чисел , если каждое из этих чисел делится на : , ,…, .

Определение 3.2. Рассмотрим целых чисел и целое число . Число называется наибольшим общим делителем чисел (НОД) чисел , если

1) является общим делителем чисел ,

2) делится на любой из общих делителей чисел .

НОД чисел обозначают .

Определение 3.3. Если , то числа называются взаимно простыми.

Свойства НОД

Теорема 3.1. НОД чисел определен однозначно с точностью до знака, т. е., если числа и – наибольшие общие делители чисел , то либо , либо .

Доказательство. Из определения НОД следует, что и , поскольку оба этих числа являются общими делителями чисел . Тогда по следствию 2 к свойству 5 делимости чисел либо , либо .

Замечание. По теореме 3.1. каждая совокупность целых чисел обладает ровно двумя НОД, отличающимися друг от друга только знаками. Поэтому можно рассматривать только случай, когда НОД чисел положителен. Далее будем считать, что .

Теорема 3.2. Пусть (т. е. число является наибольшим общим делителем чисел ). Тогда число является наибольшим по величине общим делителем этих чисел.

Доказательство. Пусть – общий делитель чисел . Тогда из определения НОД следует, что . По свойству 5 делимости чисел . Мы условились считать, что НОД чисел положителен, следовательно, . Учитывая, что , получим требуемое утверждение.

Теорема 3.3. Пусть – целые числа. Для того, чтобы число было НОД чисел и необходимо и достаточно, чтобы существовали такие взаимно простые числа и , что .

Доказательство. Необходимость. Пусть . Докажем, что существуют такие взаимно простые числа и , что . Поскольку числа и делятся на , имеем . Докажем, что числа и – искомые, т. е. . Предположим, что это утверждение неверно, это значит, что , где . Тогда , где – целые числа. Следовательно, . Значит, – общий делитель чисел и , причем . Получили, что число не является наибольшим общим делителем чисел и , что противоречит условию. Следовательно, сделанное нами предположение неверно, что и доказывает требуемое утверждение.

Достаточность. Пусть , где . Докажем, что . Из условия утверждения следует, что и , следовательно, – делитель чисел и .

Предположим, что – не является наибольшим общим делителем чисел и . Пусть . Тогда . Это значит, что , где – целое число, причем . Из определения НОД получим, что . Тогда . Из единственности частного следует, что . Значит, числа и не являются взаимно простыми, что противоречит сделанному нами предположению. Полученное противоречие доказывает справедливость утверждения.