Меню

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



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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Взаимно простыми целые числа a 1 , a 2 , … , 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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если два целых числа 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 , то он будет делить и c , и a · c . Значит, НОД ( c , b ) делит и a · c и b , следовательно, делит и НОД ( a · c , b ) .

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

Если числа из последовательности a 1 , a 2 , … , a k будут взаимно простыми по отношению к числам последовательности b 1 , b 2 , … , b m (при натуральных значениях k и m ), то их произведения a 1 · a 2 · … · a k и b 1 · b 2 · … · b m также являются взаимно простыми, в частности, a 1 = a 2 = … = a k = a и b 1 = b 2 = … = b m = b , то a k и b m – взаимно простые.

Согласно предыдущему свойству, мы можем записать равенства следующего вида: НОД ( a 1 · a 2 · … · a k , b m ) = НОД ( a 2 · … · a k , b m ) = … = НОД ( a k , b m ) = 1 . Возможность последнего перехода обеспечивается тем, что a k и b m взаимно просты по условию. Значит, НОД ( a 1 · a 2 · … · a k , b m ) = 1 .

Обозначим a 1 · a 2 · … · a k = A и получим, что НОД ( b 1 · b 2 · … · b m , a 1 · a 2 · … · a k ) = НОД ( b 1 · b 2 · … · b m , A ) = НОД ( b 2 · … · b · b m , A ) = … = НОД ( b m , A ) = 1 . Это будет справедливым в силу последнего равенства из цепочки, построенной выше. Таким образом, у нас получилось равенство НОД ( b 1 · b 2 · … · b m , a 1 · a 2 · … · a k ) = 1 , с помощью которого можно доказать взаимную простоту произведений a 1 · a 2 · … · a k и b 1 · b 2 · … · b m

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

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

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

Попарно простые числа – это последовательность целых чисел a 1 , a 2 , … , 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 . В случае с простыми числами понятия взаимной и попарной простоты будут совпадать.

Источник статьи: http://zaochnik.com/spravochnik/matematika/delimost/vzaimno-prostye-chisla/


Adblock
detector