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

Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.

  • 14 и 25 взаимно просты, так как у них нет общих делителей;
  • 15 и 25 не взаимно просты, так как у них имеется общий делитель 5;

Наглядное представление: если на плоскости построить «лес», установив на точки с целыми координатами «деревья» нулевой толщины, то из начала координат видны только деревья, координаты которых взаимно просты, см. рисунок справа как пример видимости «дерева» с координатами (9, 4).

Содержание

Обозначения [ править | править код ]

Для указания взаимной простоты чисел m <displaystyle m> и n <displaystyle n> используется обозначение [1] :

m ⊥ n . <displaystyle mperp n.>

Подобно тому, как перпендикулярные прямые не имеют общего направления, так и перпендикулярные числа не имеют общих сомножителей. [1]

Однако не все математики признают и используют это обозначение. Чаще всего используется словесная формулировка или эквивалентная запись gcd ( a , b ) = 1 <displaystyle gcd(a,b)=1> , что означает: «наибольший общий делитель чисел a и b равен 1».

Связанные определения [ править | править код ]

  • Если в наборе чисел любые два числа взаимно просты, то такие числа называются попарно взаимно простыми. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.

Примеры [ править | править код ]

  • 8, 15 — не простые, но взаимно простые.
  • 6, 8, 9 — взаимно простые (в совокупности) числа, но не попарно взаимно простые.
  • 8, 15, 49 — попарно взаимно простые.

Свойства [ править | править код ]

  • Числа a <displaystyle a>и b <displaystyle b>взаимно просты тогда и только тогда, когда выполняется одно из эквивалентных условий:
  • наибольший общий делитель a <displaystyle a>и b <displaystyle b>равен единице;
  • существуют целые x <displaystyle x>и y <displaystyle y>такие, что a x + b y = 1 <displaystyle ax+by=1>(соотношение Безу).
  • Любые два (различные) простые числа взаимно просты.
  • Если a <displaystyle a>— делитель произведения b c <displaystyle bc>, и a <displaystyle a>взаимно просто с b <displaystyle b>, то a <displaystyle a>— делитель c <displaystyle c>.
  • Если числа a 1 , … , a n <displaystyle a_<1>,ldots ,a_>— попарно взаимно простые числа, то НОК ( a 1 , … , a n ) = | a 1 ⋅ … ⋅ a n | <displaystyle (a_<1>,ldots ,a_)=|a_<1>cdot ldots cdot a_|>. Например, НОК ( 9 , 11 ) = 9 ⋅ 11 = 99 <displaystyle (9,11)=9cdot 11=99>.
  • Вероятность того, что любые k <displaystyle k>случайным образом выбранных положительных целых чисел будут взаимно просты, равна 1 ζ ( k ) <displaystyle <dfrac <1><zeta (k)>>>, в том смысле, что при N → ∞ <displaystyle N o infty >вероятность того, что k <displaystyle k>положительных целых чисел, меньших, чем N <displaystyle < extstyle >>(и выбранных случайным образом) будут взаимно простыми, стремится к 1 ζ ( k ) <displaystyle <dfrac <1><zeta (k)>>>. Здесь ζ ( k ) <displaystyle zeta (k)>— это дзета-функция Римана.
  • Дробь является несократимой тогда и только тогда, когда числитель и знаменатель взаимно просты.
  • Обобщения [ править | править код ]

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

    Применение [ править | править код ]

    Обычно число зубьев на звёздочках и число звеньев цепи в цепной передаче стремятся делать взаимно простыми, что обеспечивает равномерность износа: каждый зуб звёздочки будет поочерёдно работать со всеми звеньями цепи.

    Читайте также:  Информация о флешках в реестре

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

    Для определения взаимно простых чисел необходимо указать количество и ввести числа.

    Нажмите кнопку рассчитать и калькулятор укажет как определить взаимно простые числа.

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

    Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен 1.

    Ниже описано как определить являются ли числа 35 и 40 взаимно простыми.

    • 1 Находим наибольший общий делитель чисел: НОД(35, 40)=5.
    • 2 Наибольший общий делитель ≠ 1 следовательно числа не взаимно простые.
    Пример Определить являются ли 77 и 20 взаимно простыми числами

    .

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

    Рассмотрим на примере как определить взаимно простые числа.

    Пример Являются ли числа 42 и 55 взаимно простыми

    .

    Определим что 3 числа 10, 30, 41 являются взаимно простыми.

    Пример Проверить что числа 10, 30, 41 взаимно просты

    .

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

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

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

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

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

    Читайте также:  Значение кнопок на пульте телевизора lg

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

    Читайте также:  Биос 2016 года для асус

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

    Ссылка на основную публикацию
    Adblock detector