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