Математика на cleverstudents.ru

Делимость, признаки делимости

Взаимно простые числа – определение, примеры и свойства.

Информация этой статьи покрывает тему «взаимно простые числа». Сначала дано определение двух взаимно простых чисел, а также определение трех и большего количества взаимно простых чисел. После этого приведены примеры взаимно простых чисел, и показано, как доказать, что данные числа являются взаимно простыми. Дальше перечислены и доказаны основные свойства взаимно простых чисел. В заключение упомянуты попарно простые числа, так как они тесно связаны со взаимно простыми числами.

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

Понятие взаимно простых чисел дается как для двух целых чисел, так и для их большего числа. Сначала приведем определение двух взаимно простых чисел. Это определение дается через наибольший общий делитель чисел, так что рекомендуем сначала разобраться с материалом указанной статьи.

Из определения взаимно простых чисел следует, что два взаимно простых числа имеют лишь один положительный общий делитель, который равен единице. А всего общих делителей у двух взаимно простых чисел две штуки – это числа 1 и −1.

Приведем примеры взаимно простых чисел.

Числа 5 и 11 являются взаимно простыми. Действительно, и 5 и 11 – простые числа, следовательно, их положительным общим делителем является только число 1, что подтверждает взаимную простоту чисел 5 и 11.

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

Два составных числа 8 и −9 являются взаимно простыми. Обоснуем это. Для этого найдем наибольший общий делитель этих чисел, записав все делители чисел 8 и −9 (при необходимости смотрите статью число делителей числа, все делители числа). Делителями восьмерки является любое из чисел ±1, ±2, ±4, ±8; все делители −9 есть числа ±1, ±3, ±9. Следовательно, НОД(8, −9)=1, поэтому, по определению 8 и −9 – два взаимно простых числа.

А вот числа 45 и 500 не являются взаимно простыми, так как имеют положительный общий делитель, отличный от единицы, которым является число 5 (делимость чисел 45 и 500 на 5 очевидна, если знать признак делимости на 5). Другой парой не взаимно простых чисел является пара 3 и −201, так как 3 есть их общий положительный делитель (делимость числа −201 на 3 легко устанавливается при помощи признака делимости на 3).

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

Определение взаимно простых чисел можно расширить для трех и большего количества чисел.

Из озвученного определения следует, что если некоторый набор целых чисел имеет положительный общий делитель, отличный от единицы, то данные целые числа не являются взаимно простыми.

Приведем примеры. Три целых числа −99, 17 и −27 являются взаимно простыми. Любая совокупность простых чисел составляет набор взаимно простых чисел, к примеру, 2, 3, 11, 19, 151, 293 и 677 – взаимно простые числа. А четыре числа 12, −9, 900 и −72 не являются взаимно простыми, так как они имеют положительный общий делитель 3, отличный от 1. Числа 17, 85 и 187 тоже не взаимно простые, так как каждое из них делится на 17.

Обычно далеко не очевидно, что некоторые числа являются взаимно простыми, и этот факт приходится доказывать. Для выяснения, являются ли данные числа взаимно простыми, приходится находить наибольший общий делитель этих чисел, и на основании определения взаимно простых чисел делать вывод.

Свойства взаимно простых чисел

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

1. Числа, полученные при делении целых чисел a и b на их наибольший общий делитель, являются взаимно простыми, то есть, a:НОД(a, b) и b:НОД(a, b) – взаимно простые.

   Это свойство мы доказали, когда разбирали свойства НОД.

   Рассмотренное свойство взаимно простых чисел позволяет находить пары взаимно простых чисел. Для этого достаточно взять два любых целых числа и разделить их на наибольший общий делитель, полученные числа будут взаимно простыми.

2. Для того чтобы целые числа a и b были взаимно простыми необходимо и достаточно, чтобы существовали такие целые числа u₀ и v₀, что a·u₀+b·v₀=1.

   Докажем сначала необходимость.

   Пусть числа a и b взаимно простые. Тогда по определению взаимно простых чисел НОД(a, b)=1. А из свойств НОД мы знаем, что для целых чисел a и b верно соотношение Безу a·u₀+b·v₀=НОД(a, b). Следовательно, a·u₀+b·v₀=1.

   Осталось доказать достаточность.

   Пусть верно равенство a·u₀+b·v₀=1. Так как НОД(a, b) делит и a и b, то НОД(a, b) в силу свойств делимости должен делить сумму a·u₀+b·v₀, а значит, и единицу. А это возможно только когда НОД(a, b)=1. Следовательно, a и b – взаимно простые числа.

3. Следующее свойство взаимно простых чисел таково: если числа a и b взаимно простые, и произведение a·c делится на b, то c делится на b.

   Действительно, так как a и b взаимно простые, то из предыдущего свойства мы имеем равенство a·u₀+b·v₀=1. Умножив обе части этого равенства на c, имеем a·c·u₀+b·c·v₀=c. Первое слагаемое суммы a·c·u₀+b·c·v₀ делится на b, так как a·c делится на b по условию, второе слагаемое этой суммы также делится на b, так как один из множителей равен b, следовательно, вся сумма делится на b. А так как сумма a·c·u₀+b·c·v₀ равна c, то и c делится на b.

4. Если числа a и b взаимно простые, то НОД(a·c, b)=НОД(c, b).

   Покажем, во-первых, что НОД(a·c, b) делит НОД(c, b), а во-вторых, что НОД(c, b) делит НОД(a·c, b), это и будет доказывать равенство НОД(a·c, b)=НОД(c, b).

   НОД(a·c, b) делит и a·c и b, а так как НОД(a·c, b) делит b, то он также делит и b·c. То есть, НОД(a·c, b) делит и a·c и b·c, следовательно, в силу свойств наибольшего общего делителя он делит и НОД(a·c, b·c), который по свойствам НОД равен c·НОД(a, b)=c. Таким образом, НОД(a·c, b) делит и b и c, следовательно, делит и НОД(c, b).

   С другой стороны, НОД(c, b) делит и c и b, а так как он делит с, то также делит и a·c. Таким образом, НОД(c, b) делит и a·c и b, следовательно, делит и НОД(a·c, b).

   Так мы показали, что НОД(a·c, b) и НОД(c, b) взаимно делят друг друга, значит, они равны.

5. Если каждое из чисел a₁, a₂, …, a_k взаимно просто с каждым из чисел b₁, b₂, …, b_m (где k и m – некоторые натуральные числа), то произведения a₁·a₂·…·a_k и b₁·b₂·…·b_m есть взаимно простые числа, в частности, если a₁=a₂=…=a_k=a и b₁=b₂=…=b_m=b, то a^k и b^m – взаимно простые числа.

   Предыдущее свойство взаимно простых чисел позволяет нам записать ряд равенств вида НОД(a₁·a₂·…·a_k, b_m)=НОД(a₂·…·a_k, b_m)=…=НОД(a_k, b_m)=1, где последний переход возможен, так как a_k и b_m взаимно простые числа по условию. Итак, НОД(a₁·a₂·…·a_k, b_m)=1.

   Теперь, обозначив a₁·a₂·…·a_k=A, имеем
   НОД(b₁·b₂·…·b_m, a₁·a₂·…·a_k)=НОД(b₁·b₂·…·b_m, A)=
   =НОД(b₂·…·b_m, A)=… =НОД(b_m, A)=1
   (последний переход справедлив, в силу последнего равенства из предыдущего абзаца). Так мы получили равенство НОД(b₁·b₂·…·b_m, a₁·a₂·…·a_k)=1, которое доказывает, что произведения a₁·a₂·…·a_k и b₁·b₂·…·b_m являются взаимно простыми числами.

На этом закончим обзор основных свойств взаимно простых чисел.

Попарно простые числа – определения и примеры

Через взаимно простые числа дается определение попарно простых чисел.

Приведем пример попарно простых чисел. Числа 14, 9, 17, и −25 – попарно простые, так как пары чисел 14 и 9, 14 и 17, 14 и −25, 9 и 17, 9 и −25, 17 и −25 представляют собой взаимно простые числа. Здесь же заметим, что попарно простые числа всегда являются взаимно простыми.

С другой стороны, взаимно простые числа далеко не всегда являются попарно простыми, это подтверждает следующий пример. Числа 8, 16, 5 и 15 не являются попарно простыми, так как числа 8 и 16 не взаимно простые. Однако, числа 8, 16, 5 и 15 – взаимно простые. Таким образом, 8, 16, 5 и 15 – взаимно простые числа, но не попарно простые.

Следует особо выделить совокупность некоторого количества простых чисел. Эти числа всегда являются и взаимно простыми и попарно простыми. Например, 71, 443, 857, 991 – и попарно простые, и взаимно простые числа.

Также понятно, что когда речь идет о двух целых числах, то для них понятия «попарно простые» и «взаимно простые» совпадают.