Взаимно простые числа

Определение 5.1. Целые числа называются взаимно простыми, если их НОД равен :

Примеры.

1. Числа и – взаимно простые.

2. Числа и – не взаимно простые, так как .

Следующая теорема устанавливает необходимое и достаточное условие взаимной простоты чисел.

Теорема 5.1 (признак взаимной простоты чисел). Для того, чтобы числа и были взаимно простыми, необходимо и достаточно, чтобы нашлись такие целые числа и , что .

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

2. Достаточность. Пусть справедливо утверждение , где и – целые числа. Докажем, что . Предположим, что числа и не являются взаимно простыми: , причем . Тогда и , и по свойству делимости . Значит, , следовательно, . Полученное противоречие доказывает, что сделанное нами предположение неверно, и, тем самым, справедливо .

Следствие 1. Если числа и взаимно просты, причем и , то числа и также взаимно просты.

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

, а, значит, числа и взаимно просты.

Следствие 2. Рассмотрим целые числа , и . Если и , то .

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

следующем виде: , где и – целые числа. По определению делимости условие означает, что найдется такое целое число , что . Умножим обе части последнего равенства на , получим . Но , тогда