Взаимно простые числа
Определение 5.1. Целые числа называются взаимно простыми, если их НОД равен
:
Примеры.
1. Числа и
– взаимно простые.
2. Числа и
– не взаимно простые, так как
.
Следующая теорема устанавливает необходимое и достаточное условие взаимной простоты чисел.
Теорема 5.1 (признак взаимной простоты чисел). Для того, чтобы числа и
были взаимно простыми, необходимо и достаточно, чтобы нашлись такие целые числа
и
, что
.
Доказательство. 1. Необходимость. Пусть числа и
взаимно просты, то есть
. Тогда по теореме о линейном представлении НОД найдутся такие целые числа
и
, что
.
2. Достаточность. Пусть справедливо утверждение , где
и
– целые числа. Докажем, что
. Предположим, что числа
и
не являются взаимно простыми:
, причем
. Тогда
и
, и по свойству делимости
. Значит,
, следовательно,
. Полученное противоречие доказывает, что сделанное нами предположение неверно, и, тем самым, справедливо
.
Следствие 1. Если числа и
взаимно просты, причем
и
, то числа
и
также взаимно просты.
Доказательство. По теореме из взаимной простоты чисел и
следует, что найдутся такие целые числа
и
, что
. Из определения делимости
,
, где
и
– целые числа. Тогда
, а, значит, числа
и
взаимно просты.
Следствие 2. Рассмотрим целые числа ,
и
. Если
и
, то
.
Доказательство. По теореме условие можно записать в
следующем виде: , где
и
– целые числа. По определению делимости условие
означает, что найдется такое целое число
, что
. Умножим обе части последнего равенства на
, получим
. Но
, тогда
.
Поскольку – целое число, последнее равенство означает, что
.
Дата добавления: 2021-02-19; просмотров: 440;