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

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

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

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

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

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

    Взаимно простыми будут два таких числа 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, на что указывает соответствующий признак делимости.

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

    Пример 1

    Условие: выясните, являются ли взаимно простыми числа 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, то данные числа будут взаимно простыми.

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

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

    Взаимно простыми целые числа a1, a2, , ak, 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 является существование таких целых чисел u0 и v0, при которых равенство a·u0+b·v0=1 будет верным.

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

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

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

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

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

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

    Докажем, что НОД (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) взаимно делят друг друга, значит, они являются равными.

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

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

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

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

    Обозначим a1·a2·· ak=A и получим, что НОД (b1·b2·· bm, a1·a2··ak) =НОД (b1·b2·· bm, A)= НОД (b2··b·bm, A)= =НОД (bm, A) =1. Это будет справедливым в силу последнего равенства из цепочки, построенной выше. Таким образом, у нас получилось равенство НОД (b1·b2··bm, a1·a2··ak) =1, с помощью которого можно доказать взаимную простоту произведений a1·a2··ak и b1·b2··bm 

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

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

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

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

    Попарно простые числа – это последовательность целых чисел a1, a2, , ak, где каждое число будет взаимно простым по отношению к остальным.

    Примером последовательности попарно простых чисел может быть 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. В случае с простыми числами понятия взаимной и попарной простоты будут совпадать.

    Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
    Средняя оценка статьи
    4,7 из 5 (18 голосов)