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

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

  1. Ragewind Ответить

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

    Взаимно простые числа обладают рядом свойств. Рассмотрим основные свойства взаимно простых чисел.
    Числа, полученные при делении целых чисел 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. ДеМо(НеСс) Ответить

    Рассмотрим свойства взаимно простых чисел.
    ПРЕДЛОЖЕНИЕ 2.9. Целые числа взаимно простые тогда и только тогда, когда единица представима в виде целочисленной линейной комбинации этих чисел.
    Доказательство. Если числа взаимно простые, то их наибольший общий делитель единица представим согласно теореме 2.5 в виде целочисленной линейной комбинации этих чисел.
    Обратно: если единица представима в виде целочисленной линейной комбинации чисел то в силу предложения 2.6 единица есть наибольший общий делитель этих чисел. Поэтому числа взаимно простые.
    ПРЕДЛОЖЕНИЕ 2.10. Целые числа взаимно простые тогда и только тогда, когда они не имеют общего простого делителя.
    Доказательство предоставляется читателю.
    ТЕОРЕМА 2.11. Если целое число делит произведение двух целых чисел и взаимно простое с одним из сомножителей, то оно делит другой сомножитель.
    Доказательство. Пусть числа а и b взаимно простые и а делит . Докажем, что а делит c. Так как числа а и b взаимно простые, то существуют такие целые числа что

    Умножив обе части равенства на с, получим . Кроме того, а делит Поэтому а делит , т. е. а делит с.

  4. Nightcliff Ответить

    Макеты страниц

    5. Взаимно простые числа.

    Два целых числа называются взаимно простыми, если их н.о.д. равен 1.
    Ясно, что если d есть наибольший общий делитель целых чисел а и b, то и суть целые взаимно простые числа. Действительно, то, что эти числа целые, следует из того, что d — общий делитель для а и b. Если — наибольший общий делитель и а и b делятся на , откуда следует, что иначе не был бы наибольшим общим делителем для а и b.
    Предложение 5. Для того чтобы целые числа а и b были взаимно простыми, необходимо и достаточно существование целых чисел таких, что
    Предложение 5 можно сформулировать и в других терминах: для того чтобы неопределенное уравнение имело решение в целых числах, необходимо и достаточно, чтобы а и b были взаимно просты.
    Доказательство. Пусть а и b взаимно просты. Тогда их н.о.д., равный 1, имеет линейное представление: . Пусть теперь существуют такие, что . Тогда н.о.д. (а, b) делит , а следовательно, и их сумму, равную 1. Но 1 не имеет натуральных делителей, кроме 1, так что равен 1. Предложение доказано полностью.
    Предложение 6. Если целые числа взаимно просты с целым числом b, то их произведение тоже взаимно просто с b.
    Доказательство. Существуют целые такие, что в силу предложения 5. Перемножая эти равенства, получим после очевидных преобразований

    откуда, в силу того же предложения, числа и b взаимно просты, ибо целые числа.
    Предложение 7. Если целые числа все взаимно просты с b, то произведение тоже взаимно просто с b.
    Доказательство. Применим метод математической индукции. При предложение верно в силу предложения 6. Допустим, что оно верно для произведения множителей, и в этом предположении докажем его для k множителей. Запишем как . Первый множитель взаимно прост с b по условию. Второй взаимно прост с b в силу индуктивного предположения. Следовательно, мы можем применить предложение 6 и заключить, что взаимно просто с b, что и требовалось доказать.
    Предложение 8. Если целые числа таковы, что каждое число взаимно просто с каждым числом , то их произведения взаимно просты.
    Доказательство. Применив m раз предложение 7 к числам получим, что числа взаимно просты с числом Применяя еще раз предложение 7, получим, что взаимно просто с что и требовалось доказать.
    Предложение 9. Если целые числа а и b взаимно просты, то при натуральных k и числа тоже взаимно просты.
    Для доказательства достаточно в предложении 8 положить .
    Предложение 10. Если произведение двух целых чисел а и b делится на целое число с и первый множитель а взаимно прост с с, то b делится на с.
    Доказательство. По условию а и с взаимно просты, так что существуют целые такие, что . Умножив это равенство на b, получим . Первое слагаемое левой части делится на с по условию, второе делится на с тривиальным образом. Следовательно, и их сумма b делится на с, что и требовалось доказать.
    Предложение 11. Если целое число а делится на целые взаимно простые числа , то а делится и на их произведение.
    Доказательство. Пусть при целом с. По условию а делится на взаимно просто с . Следовательно, согласно предложению 8 число с делится на при целом . Поэтому , что и требовалось доказать.
    Установленные предложения очень просты и кажутся почти тривиальными. Тем не менее из них можно вывести некоторые не совсем тривиальные следствия.
    Выведем, например, что степень с натуральным показателем дробного рационального положительного числа не может быть целым числом.
    Действительно, пусть — дробное рациональное число с целым положительным знаменателем b и с целым числителем а. Без нарушения общности можно считать, что числитель и знаменатель взаимно просты, этого можно добиться за счет сокращения на наибольший общий делитель. Пусть это выполнено. Ясно, что иначе было бы целым. Пусть — натуральное число. Тогда . В силу предложения взаимно просты. Поэтому не может делиться на так что не является целым числом.
    Из доказанного следует далее, что если целое положительное число с не является степенью целого числа (при натуральном ), то оно не является степенью дробного рационального числа. Поэтому целое число, ибо иррациональное. Так, числа (пропускаются целые все иррациональны, также иррациональны и числа (пропускаются целые ) и т. д.

  5. VideoAnswer Ответить

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

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