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

10 декабря 2023
12 минут
4 930

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

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

Что такое взаимно простые числа

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

Определение 1

Взаимно простыми будут два таких числа $a$ и $b$ , наибольший общий делитель которых равен $1$ , т.е. НОД $(a, b) = 1$ .

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

Какие можно привести примеры взаимно простых чисел? Например, такой парой будут $5$ и $11$ . Они имеют только один общий положительный делитель, равный $1$ , что является подтверждением их взаимной простоты.

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

Это утверждение иллюстрирует следующий пример: составные числа $- 9$ и $8$ образуют взаимно простую пару. Докажем это, вычислив их наибольший общий делитель. Для этого запишем все их делители (рекомендуем перечитать статью о нахождении делителей числа). У $8$ это будут числа $\pm 1, \pm 2, \pm 4, \pm 8$ , а у $9$ – $\pm 1, \pm 3, \pm 9$ . Выбираем из всех делителей тот, что будет общим и наибольшим – это единица. Следовательно, если НОД $(8, - 9) = 1$ , то $8$ и $- 9$ будут взаимно простыми по отношению друг к другу.

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

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

Пример 1

Условие: выясните, являются ли взаимно простыми числа $275$ и $84$ .

Решение

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

Вычисляем наибольший общий делитель, используя алгоритм Евклида: $275 = 84 \cdot 3 + 23, 84 = 23 \cdot 3 + 15, 23 = 15 \cdot 1 + 8, 15 = 8 \cdot 1 + 7, 8 = 7 \cdot 1 + 1, 7 = 7 \cdot 1$ .

Ответ: поскольку НОД $(84, 275) = 1$ , то данные числа будут взаимно простыми.

Как мы уже говорили раньше, определение таких чисел можно распространить и на случаи, когда у нас есть не два числа, а больше.

Определение 2

Взаимно простыми целые числа $a_{1}, a_{2}, \dots, a_{k}, k > 2$ будут тогда, когда они имеют наибольший общий делитель, равный $1$ .

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

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

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

Пример 2

Условие: определите, являются ли числа $331, 463$ и $733$ взаимно простыми.

Решение

Сверимся с таблицей простых чисел и определим, что все три этих числа в ней есть. Тогда их общим делителем может быть только единица.

Ответ: все эти числа будут взаимно простыми по отношению друг к другу.

Пример 3

Условие: приведите доказательство того, что числа $- 14, 105, - 2 107$ и $- 91$ не являются взаимно простыми.

Решение

Начнем с выявления их наибольшего общего делителя, после чего убедимся, что он не равен $1$ . Поскольку у отрицательных чисел те же делители, что и у соответствующих положительных, то НОД $(- 14, 105, 2 107, - 91) =$ НОД $(14, 105, 2 107, 91)$ . Согласно правилам, которые мы привели в статье о нахождении наибольшего общего делителя, в данном случае НОД будет равен семи.

Ответ: семь больше единицы, значит, взаимно простыми эти числа не являются.

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

Такие числа имеют некоторые практически важные свойства. Перечислим их по порядку и докажем.

Определение 3

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

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

Определение 4

Необходимым и достаточным условием взаимной простоты чисел $a$ и $b$ является существование таких целых чисел $u_{0}$ и $v_{0}$ , при которых равенство $a \cdot u_{0} + b \cdot v_{0} = 1$ будет верным.

Доказательство 1

Начнем с доказательства необходимости этого условия. Допустим, у нас есть два взаимно простых числа, обозначенных $a$ и $b$ . Тогда по определению этого понятия их наибольший общий делитель будет равен единице. Из свойств НОД нам известно, что для целых $a$ и $b$ существует соотношение Безу $a \cdot u_{0} + b \cdot v_{0} =$ НОД $(a, b)$ . Из него получим, что $a \cdot u_{0} + b \cdot v_{0} = 1$ . После этого нам надо доказать достаточность условия. Пусть равенство $a \cdot u_{0} + b \cdot v_{0} = 1$ будет верным, в таком случае, если НОД $(a, b)$ делит и $a$ , и $b$ , то он будет делить и сумму $a \cdot u_{0} + b \cdot v_{0}$ , и единицу соответственно (это можно утверждать, исходя из свойств делимости). А такое возможно только в том случае, если НОД $(a, b) = 1$ , что доказывает взаимную простоту $a$ и $b$ .

В самом деле, если $a$ и $b$ являются взаимно простыми, то согласно предыдущему свойству, будет верным равенство $a \cdot u_{0} + b \cdot v_{0} = 1$ . Умножаем обе его части на $c$ и получаем, что $a \cdot c \cdot u_{0} + b \cdot c \cdot v_{0} = c$ . Мы можем разделить первое слагаемое $a \cdot c \cdot u_{0} + b \cdot c \cdot v_{0}$ на $b$ , потому что это возможно для $a \cdot c$ , и второе слагаемое также делится на $b$ , ведь один из множителей у нас равен $b$ . Из этого заключаем, что всю сумму можно разделить на $b$ , а поскольку эта сумма равна $c$ , то c можно разделить на $b$ .

Определение 5

Если два целых числа $a$ и $b$ являются взаимно простыми, то НОД $(a \cdot c, b) =$ НОД $(c, b)$ .

Доказательство 2

Докажем, что НОД $(a \cdot c, b)$ будет делить НОД $(c, b)$ , а после этого – что НОД $(c, b)$ делит НОД $(a \cdot c, b)$ , что и будет доказательством верности равенства НОД $(a \cdot c, b) =$ НОД $(c, b)$ .

Поскольку НОД $(a \cdot c, b)$ делит и $a \cdot c$ и $b$ , а НОД $(a \cdot c, b)$ делит $b$ , то он также будет делить и $b \cdot c$ . Значит, НОД $(a \cdot c, b)$ делит и $a \cdot c$ и $b \cdot c$ , следовательно, в силу свойств НОД он делит и НОД $(a \cdot c, b \cdot c)$ , который будет равен $c \cdot$ НОД $(a, b) = c$ . Следовательно, НОД $(a \cdot c, b)$ делит и $b$ и $c$ , следовательно, делит и НОД $(c, b)$ .

Также можно сказать, что поскольку НОД $(c, b)$ делит и $c$ , и $b$ , то он будет делить и $c$ , и $a \cdot c$ . Значит, НОД $(c, b)$ делит и $a \cdot c$ и $b$ , следовательно, делит и НОД $(a \cdot c, b)$ .

Таким образом, НОД $(a \cdot c, b)$ и НОД $(c, b)$ взаимно делят друг друга, значит, они являются равными.

Определение 6

Если числа из последовательности $a_{1}, a_{2}, \dots, a_{k}$ будут взаимно простыми по отношению к числам последовательности $b_{1}, b_{2}, \dots, b_{m}$ (при натуральных значениях $k$ и $m$ ), то их произведения $a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}$ и $b_{1} \cdot b_{2} \cdot \dots \cdot b_{m}$ также являются взаимно простыми, в частности, $a_{1} = a_{2} = \dots = a_{k} = a$ и $b_{1} = b_{2} = \dots = b_{m} = b$ , то $a^{k}$ и $b^{m}$ – взаимно простые.

Доказательство 3

Согласно предыдущему свойству, мы можем записать равенства следующего вида: НОД $(a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}, b_{m}) =$ НОД $(a_{2} \cdot \dots \cdot a_{k}, b_{m}) = \dots =$ НОД $(a_{k}, b_{m}) = 1$ . Возможность последнего перехода обеспечивается тем, что $a_{k}$ и $b_{m}$ взаимно просты по условию. Значит, НОД $(a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}, b_{m}) = 1$ .

Обозначим $a_{1} \cdot a_{2} \cdot \dots \cdot a_{k} = A$ и получим, что НОД $(b_{1} \cdot b_{2} \cdot \dots \cdot b_{m}, a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}) =$ НОД $(b_{1} \cdot b_{2} \cdot \dots \cdot b_{m}, A) =$ НОД $(b_{2} \cdot \dots \cdot b \cdot b_{m}, A) = \dots =$ НОД $(b_{m}, A) = 1$ . Это будет справедливым в силу последнего равенства из цепочки, построенной выше. Таким образом, у нас получилось равенство НОД $(b_{1} \cdot b_{2 \cdot} \dots \cdot b_{m}, a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}) = 1$ , с помощью которого можно доказать взаимную простоту произведений $a_{1} \cdot a_{2} \cdot \dots \cdot a_{k}$ и $b_{1} \cdot b_{2} \cdot \dots \cdot b_{m}$

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

Понятие попарно простых чисел

Зная, что из себя представляют взаимно простые числа, мы можем сформулировать определение попарно простых чисел.

Определение 7

Попарно простые числа – это последовательность целых чисел $a_{1}, a_{2}, \dots, a_{k}$ , где каждое число будет взаимно простым по отношению к остальным.

Примером последовательности попарно простых чисел может быть $14, 9, 17$ , и $- 25$ . Здесь все пары ( $14$ и $9$ , $14$ и $17$ , $14$ и $- 25$ , $9$ и $17$ , $9$ и $- 25$ , $17$ и $- 25$ ) взаимно просты. Отметим, что условие взаимной простоты является обязательным для попарно простых чисел, но взаимно простые числа будут попарно простыми далеко не во всех случаях. Например, в последовательности $8, 16, 5$ и $15$ числа не являются таковыми, поскольку $8$ и $16$ не будут взаимно простыми.

Также следует остановиться на понятии совокупности некоторого количества простых чисел. Они всегда будут и взаимно, и попарно простыми. Примером может быть последовательность $71, 443, 857, 991$ . В случае с простыми числами понятия взаимной и попарной простоты будут совпадать.