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

6 ответов на вопрос “Как доказать что числа не взаимно простые?”

  1. MULTIK Ответить

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

  2. Blackray Ответить

    Взаимно простые числа обладают рядом свойств. Рассмотрим основные свойства взаимно простых чисел.
    Числа, полученные при делении целых чисел a и b на их наибольший общий делитель, являются взаимно простыми, то есть, a:НОД(a, b) и b:НОД(a, b) – взаимно простые.
    Это свойство мы доказали, когда разбирали свойства НОД.
    Рассмотренное свойство взаимно простых чисел позволяет находить пары взаимно простых чисел. Для этого достаточно взять два любых целых числа и разделить их на наибольший общий делитель, полученные числа будут взаимно простыми.
    Для того чтобы целые числа a и b были взаимно простыми необходимо и достаточно, чтобы существовали такие целые числа u0 и v0, что a·u0+b·v0=1.
    Докажем сначала необходимость.
    Пусть числа a и b взаимно простые. Тогда по определению взаимно простых чисел НОД(a, b)=1. А из свойств НОД мы знаем, что для целых чисел a и b верно соотношение Безу a·u0+b·v0=НОД(a, b). Следовательно, a·u0+b·v0=1.
    Осталось доказать достаточность.
    Пусть верно равенство a·u0+b·v0=1. Так как НОД(a, b) делит и a и b, то НОД(a, b) в силу свойств делимости должен делить сумму a·u0+b·v0, а значит, и единицу. А это возможно только когда НОД(a, b)=1. Следовательно, a и b – взаимно простые числа.
    Следующее свойство взаимно простых чисел таково: если числа a и b взаимно простые, и произведение a·c делится на b, то c делится на 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, следовательно, вся сумма делится на b. А так как сумма a·c·u0+b·c·v0 равна 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, а так как он делит с, то также делит и a·c. Таким образом, НОД(c, b) делит и a·c и b, следовательно, делит и НОД(a·c, b).
    Так мы показали, что НОД(a·c, b) и НОД(c, b) взаимно делят друг друга, значит, они равны.
    Если каждое из чисел a1, a2, …, ak взаимно просто с каждым из чисел b1, b2, …, bm (где k и m – некоторые натуральные числа), то произведения a1·a2·…·ak и b1·b2·…·bm есть взаимно простые числа, в частности, если a1=a2=…=ak=a и b1=b2=…=bm=b, то ak и bm – взаимно простые числа.
    Предыдущее свойство взаимно простых чисел позволяет нам записать ряд равенств вида НОД(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·…·bm, A)=… =НОД(bm, A)=1
    (последний переход справедлив, в силу последнего равенства из предыдущего абзаца). Так мы получили равенство НОД(b1·b2·…·bm, a1·a2·…·ak)=1, которое доказывает, что произведения a1·a2·…·ak и b1·b2·…·bm являются взаимно простыми числами.
    На этом закончим обзор основных свойств взаимно простых чисел.

  3. VideoAnswer Ответить

  4. VideoAnswer Ответить

  5. VideoAnswer Ответить

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *