Научная библиотека

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

Пусть а и b — два целых числа, из которых по крайней мере одно отлично от нуля. Наибольшим общим делителем чисел а и b называется наибольшее натуральное число d, являющееся делителем как для а, так и для b.

Например, наибольший общий делитель чисел —6 и 10 равен 2, наибольший общий делитель чисел —6 и 0 есть 6, наибольший общий делитель чисел —6 и 5 равен 1.

Наибольший общий делитель чисел а и b обозначается или просто последнее обозначение применяется только в случае, если в том же контексте символ не используется в каком-либо другом смысле (например, координаты точки на плоскости или скалярное произведение векторов а и b и т. д.).

Важное свойство наибольшего общего делителя сформулировано в следующей теореме.

Теорема 4. Пусть а, b — целые числа, одно из которых отлично от 0, и пусть наибольший общий делитель. Тогда (1) существуют целые числа такие, что ; (2) если d — какой-либо общий делитель чисел а и b, то d делится на

Доказательство. Рассмотрим бесконечное множество М целых чисел, состоящее из чисел , где u и v независимо друг от друга пробегают все целые числа: не

Множество М содержит число а, оно получается при содержит b (при содержит 0 (при и бесконечно много других целых чисел.

Установим, что если два числа и у принадлежат М и , то остаток при делении х на у тоже принадежит М. Действительно, значит, что . При некоторых целых Пусть так что есть остаток при делении на . Тогда Числа целые, следовательно,

Выберем теперь в множестве М наименьшее положительное число d. Покажем, что а и b делятся на d. Пусть — остаток при делении а на d. Так как а и d принадлежат М, то, в силу только сказанного, принадлежит М. Но — наименьшее положительное число, содержащееся в М.

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