Меню

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

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

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

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

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

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

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

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

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

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

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

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

Очевидно, что данные числа не являются простыми, поэтому мы не можем сразу говорить о взаимной простоте чисел 84 и 275 , и нам придется вычислять НОД. Используем алгоритм Евклида для нахождения НОД: 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 . Этим доказано, что числа 84 и 275 взаимно простые.

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

Целые числа a1, a2, …, ak , k>2 называются взаимно простыми, если наибольший общий делитель этих чисел равен единице.

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

Приведем примеры. Три целых числа −99 , 17 и −27 являются взаимно простыми. Любая совокупность простых чисел составляет набор взаимно простых чисел, к примеру, 2 , 3 , 11 , 19 , 151 , 293 и 677 – взаимно простые числа. А четыре числа 12 , −9 , 900 и −72 не являются взаимно простыми, так как они имеют положительный общий делитель 3 , отличный от 1 . Числа 17 , 85 и 187 тоже не взаимно простые, так как каждое из них делится на 17 .

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

Являются ли числа 331 , 463 и 733 взаимно простыми?

Заглянув в таблицу простых чисел, мы обнаружим, что каждое из чисел 331 , 463 и 733 – простое. Следовательно, они имеют единственный положительный общий делитель – единицу. Таким образом, три числа 331 , 463 и 733 есть взаимно простые числа.

источник

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

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

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

источник

Натуральное число $p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.

Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.

Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3, 6$. Значит делителем числа $6$ будут числа $1,2,3,6.$

Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.

Составным называют число, у которого кроме единицы и самого себя есть другие делители.

Примером простого числа может являться число $13$, примером составного число $14.$

Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.

Попробуй обратиться за помощью к преподавателям

Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД и сравнить его с $1$.

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

$8, 15$ – не простые, но взаимно простые.

$6, 8, 9$ – взаимно простые числа, но не попарно взаимно простые.

$8, 15, 49$ – попарно взаимно простые.

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

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Например, разложим на простые множители число $180$:

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$

Воспользуемся свойством степеней, тогда получим,

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

Каноническое разложение натурального числа в общем виде имеет вид:

$m=p^_1\cdot p^_2\cdot \dots \dots ..\cdot p^_k$

где $p_1,p_2\dots \dots .p_k$- простые числа, а показатели степеней- натуральные числа.

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

Найти наибольший общий делитель чисел $180$ и $240$.

Решение: Разложим числа на простые множества с помощью канонического разложения

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тогда $180=2^2\cdot 3^2\cdot 5$

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тогда $240=2^4\cdot 3\cdot 5$

Теперь найдем НОД этих чисел, для этого выберем степени с одинаковым основанием и с наименьшим показателем степени, тогда

$НОД \ (180;240)= 2^2\cdot 3\cdot 5=60$

Составим алгоритм нахождения НОД с учетом канонического разложения на простые множители.

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

  1. разложить числа на простые множители в каноническом виде
  2. выбрать степени с одинаковым основанием и с наименьшим показателем степени входящих в состав разложения этих чисел
  3. Найти произведение чисел, найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.

Определить, будут ли простыми, взаимно простыми числами числа $195$ и $336$.

Решение: Воспользуемся для разложения на множители каноническим разложением:

$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

Мы видим, что НОД этих чисел отличен от $1$, значит числа не взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.

Определить, будут ли простыми, взаимно простыми числами числа $39$ и $112$.

Решение: Воспользуемся для разложения на множители каноническим разложением:

$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят множители, помимо $1$ и самого числа, значит простыми числа так же являться не будут, а будут являться составными.

Читайте также:  Суп с мясом как готовить

Определить будут ли простыми, взаимно простыми числами числа $883$ и $997$.

Решение: Воспользуемся для разложения на множители каноническим разложением:

Мы видим, что НОД этих чисел равен $1$, значит числа взаимно простые. Также мы видим, что в состав каждого из чисел входят только множители, равные $1$ и самому числу, значит числа будут являться простыми.

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

источник

Целые числа а1 , … , ап (n 2), не равные одновременно нулю, назовём взаимно простыми (в совокупности), если НОД(а1 , … , ап) = 1, и попарно взаимно простыми, если для любых i j (1 i, j n) выполнено условие НОД(аi , aj) = 1. В случае п = 2 эти понятия совпадают, но различны в общем случае, как показывает следующий пример:

Пример: Числа 2, 3, 4 взаимно просты в совокупности (т.к. (2, 3, 4) = = ((2, 3), 4) = (1, 4) = 1), но не попарно взаимно просты ((2, 4) = 2 1).

1 . Если D = НОД(а1 , … , ап), то целые числа , … ,взаимно просты в совокупности.

Из свойства 2 легко вывести следующие два свойства:

3 . Целые числа а и b взаимно просты тогда и только тогда, когда существуют целые числа х, у со свойством ах + by = 1.

а взаимно просто с т и b взаимно просто с т,

произведение аb взаимно просто с т.

Это доказывается индукцией по п. Базу индукции (п = 2) обеспечивает свойство 5 . Предположим, что эквивалентность условий уже доказана для п = k 2 и докажем её для п = k + 1. Имеем

i взаимно просты с т (1 i k) и ak+1 взаимно просто с т)

1 ak взаимно просто с т и ak+1 взаимно просто с т)

(произведение (а1 ak)ak+1 взаимно просто с т),

что и требовалось доказать.

В самом деле, если bc = аd, то учитывая существование целых чисел х, у со свойством ах + by = 1, получим

Обратная импликация очевидна.

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

Упражнения: 1. Проанализируйте доказательства свойств делимости нацело и упростите некоторые из них, применив свойство 7 .

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

источник

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

Заметьте, например, что числа 4 и 9 взаимно просты, но по отдельности ни одно из них не является простым. А число 1 взаимно просто с любым числом, в том числе и с самим собой.

Для этого определения совершенно несущественно, что чисел только два — оно буквально переносится на любое количество натуральных чисел. Например, числа 6, 10, 15 взаимно просты, хотя никакие два из них взаимно простыми, очевидно, не являются.

Свойство взаимной простоты переносится и на множество целых чисел. При этом исходное определение — для натуральных чисел — естественным образом корректируется: целое число всегда имеет два делителя — 1 и -1, так что два целых числа называются взаимно простыми, если их общими делителями являются только 1 и -1.

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

Отметим также, что иногда встречается не совсем аккуратная формулировка типа «два числа — натуральных или целых — называются взаимно простыми, если они не имеют общих делителей». В этом случае как бы забывается о 1 и -1. Такая «забывчивость» оправдана тем, что 1 и -1 — тривиальные делители, они всегда есть, и эту мелочь можно для краткости лишь подразумевать.

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

Напомним, что целое число называют простым, если простым числом является его модуль — натуральное число. Такое обобщение школьного понятия простого числа вполне естественно: ведь главное — это возможность разумного, нетривиального разложения числа на множители, а с этой точки зрения числа, скажем, 5 и -5 вполне равноправны: разложение -5 = (-5) неинтересно, неразумно, тривиально.

Для взаимно простых целых чисел чрезвычайно важным и полезным с точки зрения задач является следующий критерий взаимной простоты двух целых чисел: целые числа a и b взаимно просты тогда и только тогда, когда существуют такие целые числа u и v, что au+ bv = 1.

Это свойство, однако, явно неверно, если говорить только о натуральных числах: очевидно, не существует таких натуральных чисел u и v, что 2u + Зv = 1.

На основании именно этого свойства можно доказать — независимо от основной теоремы, что если произведение двух целых чисел делится на простое число р, то хотя бы одно из этих чисел делится на р. В самом деле, если а не делится на р, то а и р взаимно просты, а тогда для некоторых u и v выполняется равенство au + рv = 1, откуда abu + bрv = b, так что b делится на р.

Более того, это утверждение в действительности является главным для доказательства основной теоремы арифметики.

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

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

источник

Дата добавления: 2014-05-19 ; просмотров: 2574 ; Нарушение авторских прав

Два числа а ив называются взаимно простыми, если их НОД равен единице. П: числа 5 и 8 взаимно простые, т.к.D(5, 8)=1. Числа 5, 4 и 16 также взаимно простые числа, т.к.D(5,4,16)=1. Cвойства: 1.Если нат.числа а и в не делятся на простое число р, то числа а и р взаимно простые. 2.Если числа а взаимно простые с каждым из чисел в и с, то число а взаимно простое и с произведение этих чисел. 3.Если произведение чисел а и в делится на число с, а числа в и с взаимно простые, то число а делится на с. 4.Если произведение двух нат.чисел а и в делится на простое число р, тохотя бы одно из этих чисел делится на р. 5.Частное от деления данных чисел а и в на их НОД яв-ся взаимно простыми числами. П: сократим дробь . При сокращении дробей числитель и знаменатель дроби делят на их НОД. В результате должна получиться несократимая дробь,т.е.дробь, у которой числитель и знаменатель будут взаимно простые числа. Найдём D(36,96)= 12. Будем иметь: Числа 3 и 8 взаимно простые, значит, дробь полностью сократили.

Общие кратные. Свойства наименьшего общего кратного.

Число с называется общим кратным чисел а и в, если число с делится на а и на в. П: для чисел 12 и 15 общим кратным яв-ся числа 60, 120, 180, 240, 300, 360. Наибольшего общего кратного для любых чисел не существует. Наименьшее общее кратное на мн.целых неотриц.чисел для любых а и в- это число 0ю Поэтому это понятие рассматривают на мн.нат.чисел. НОК чисел а и в называется наименьшее число, которое делится на каждое из данных чисел. Обозначается: НОК(а,в) или К(а,в). П: для чисел 12 и 15 НОК яв-ся число 60, т.е.К(12,15)=60. Свойства НОК: 1.НОК чисел а и в не меньше наибольшего из этих чисел. Док-во: пусть а в и К(а,в)=м. Тогда м а и м в, значит, м а и м в. Неравенство м а доказывает утверждение теоремы. 2.Если а делится на в, то К(а,в)=а. Док-во: т.к.а в и а а, то К(а,в)=а. 3.Каждое общее кратное чисел а и в делится на их наименьшее общее кратное. Док-во: пусть М- произвольное общее кратное чисел а и в, и м- НОК этих чисел. Т.к.М м, то применим к ним теорему о делении с остатком. Получим: М=мq+r, где 0 r м. Поскольку М а и м а, то по свойству транзитивности отношения делимости r а. Аналогично док-ся, что r в. Значит,r- общее кратное чисел а и в. Если r- нат.число, то r м противоречит тому, что м-НОК. Поэтому r=0 и М=мq, следовательно, М м. 4.Каждое число, которое делится на К(а,в) яв-ся общим кратным чисел а и в. 5.Если с произвольное число, то К(ас,вс)= с К(а,в). П: найдём рациональным приёмом К(620,360). Т.к. 620=20 31, 360=20∙18, то К(620, 360)= 20∙К(31,18). Т.к.числа 31 и 18 взаимно простые, то К(31,18)= 31∙18=558. Тогда К(620, 360)= 20∙558=11160.

Нахождение НОД и НОК по каноническому виду.

Представление числа в виде произведения простых чисел называется разложением этого числа на простые множители. Раскладывая числа на простые множители, используют признаки деления на 2,3,5 и др. П: 720=2 ∙2∙2∙2∙3∙3∙5

Произведение одинаковых множителей принято заменять степенью: 720=2 4 ∙3 2 ∙ 5. Такое представление числа 720 называют каноническим видом этого числа. Алгоритм нахождения НОД: 1.Записать каждое из данных чисел в каноническом виде. 2.Выписать все общие простые множители канонических разложений с наименьшим показателем степени. 3.Найти произведение полученных степеней простых чисел. П: найдём НОД чисел 525 и 630. Т.к. 525=3∙5 2 ∙7, 630=2∙3 2 ∙5∙7, то D(525,630)= 3∙5∙7=105. Алгоритм нахождения НОК: 1.Записать каждое из данных чисел в каноническом виде. 2.Выписать все простые множители, которые входят хотя бы в одно из канонических разложений, с наибольшим показателем степени. 3.Найти произведение полученных степеней простых чисел. П: найдём НОК чисел 525 и 630. Т.к. 525=3∙5 2 ∙7, 630=2∙3 2 ∙5∙7, тогда К(525,630)= 2∙3 2 ∙5 2 ∙7=3150.

Читайте также:  Как укрывать клематисы на зиму в сибири

Арифметические операции над десятичными дробями. Понятие процента. Задачи на проценты.

Сложение (вычитание)десятичных дробей выполняется по алгоритму: 1)записывают слагаемые (уменьшаемое и вычитаемое) так, чтобы запятые были под запятыми; 2)не обращая внимания на запятые, выполняют действие по правилу сложения (вычитания) нат.чисел; 3)в полученной сумме (разности) запятую ставят под запятой. Алгоритм умножения десятичных дробей следует из алгоритма умножения обыкновенных дробей: m p mp

10 n 10 s = 10 n + s .

10 n + s в виде десятичной дроби, надо в десятичной записи нат.числа мр отделить запятой п+s последних цифр. Алгоритм: 1)рассматривают множители как нат.чис:ла; 2)находят произведение полученных двух нат.чисел; 3)в произведении отделяют запятой столько последних цифр, сколько их в обоих множителях вместе. Деление: 1)делимое и делитель увеличивают во столько раз, чтобы делитель стал целым числом (перенося запятую вправо); 2)выполняют деление так, как деление нат.чисел; 3если целую часть делимого разделили, в частном ставят запятую и продолжают деление. П: 30,21:0,003= 30210:3=10070. Процентом называют одну сотую часть и обозначают 1%. 1%= = 0,01; 2%=0,02; 25%= 0,25%; р%= .

Простые задачи на проценты: 1.Найти р% от целого числа в. Решение имеет вид: в:100 р= в . П: в книге 140 страниц, из них прочитано 30 %. Сколько страниц прочитано? 140 0,3=42 стр. 2.Найти целое число, если р% его составляют в.Решение: в:р 100=в: . П: найти объём бассейна, если 75% его составляют 282 м 2 . 282:0,75=376 м 2 . 3.Найти процентное отношение чисел а и в. Решение: ∙100%. П: В 8 кг раствора соли содержится 6,8 кг воды. Каков процент содержания воды в растворе? 6,8:8∙100=85%

Преобразование обыкновенных дробей в десятичные.

Перевод обыкновенной дроби в десятичную дробь осуществляется делением числителя дроби на её знаменатель. Если процесс деления конечный, то в результате деления числителя на знаменатель получается конечная десятичная дробь. В противном случае получается бесконечная десятичная дробь. П: 1) =3:20= 0,15- конечная десятичная дробь; 2) = 13:75= 0,173333…-бесконечная десятичная дробь. Теорема: для того чтобы несократимая обыкновенная дробь была равна конечной десятичной дроби, необходимо и достаточно, чтобы в каноническое разложение знаменателя входили лишь множители 2 или 5. Док-во: необходимость- пусть = и дробь – несократимая. Тогда по признаку равенства дробей имеем: м 10 у = nk. Из этого равенства следует, что м 10 у делится на п. Т.к.дробь несократимая, т.е.м и п- взаимно простые числа, то 10 у делится на п, а это значит, п=2 а 5 в , где – некоторые целые числа. Достаточность- пусть п=2 а 5 в , где – некоторые целые числа, причём, – наибольшее из чисел . Тогда

m m 2 y – f 5 y – d m 2 y -а 5 y -в м 2 y – a 5 y -в

п =2 а 5 в 2 y – a 5 y -в = 2 у 5 у = 10 у

Из этой теоремы следует другой способ обращения обыкновенной дроби в десятичную дробь- это умножение числителя и знаменателя на такое число, чтобы знаменатель стал степенью числа 10

Бесконечные десятичные дроби.

Бесконечная десятичная дробь, у которой одна или несколько цифр после запятой повторяются, называется периодической десятичной дробью, а повторяющаяся группа цифр называется периодом. П: = 0,1363636…= 0,1(36); =0,6296296…= 0,(629). Бесконечную периодическую десятичную дробь, у которой период начинается сразу после запятой, называют чисто периодической дробью. Если между запятой и периодом находится группа цифр, то такую дробь называют смешанной периодической. П: 0,(629); 0,(27)- чисто периодические десятичные дроби; 0,1(36); 0,5(27)- смешанные периодические десятичные дроби. Утверждения: 1)если знаменатель несократимой обыкновенной дроби взаимно прост с числом 10, то такая дробь обращается в чисто периодическую. 2если знаменатель несократимой обыкновенной дроби имеет вид п=2 а 5 в р, где р и 10- взаимно простые числа, – целые неотриц.числа, то такая дробь обращается в смешанную периодическую десятичную дробь.

Отрицательные действительные числа. Нуль.Модуль действительного числа. Противоположные числа.

Во мн.R+ полож.действит.чисел не всегда выполнима операция вычитания (н.,разность 2-5 не яв-ся полож.числом). Всё это привело к необходимости введения новых чисел, которые были названы отрицательными. Поставим в соответствие каждому положительному действительному числу х число –х. Назовём его отрицательным действительным числом. Множество всех отрицательных действительных чисел обозначим R . Объединение мн.R+,R и <0>называют множеством действительных чисел и обозначают R. Согласно определению имеем: R=R+ R <0>, где R+ R= , R+ <0>= , R <0>= . Если первоначальное значение величины было х, потом стало у, где х,у R+, то изменение у-х величины будет выражаться положительным действительным числом, если х у, и будет выражаться отрицательным числом, если х у, т.е.её изменение будет: у-х=-(х-у). Любое действ.число можно отметить на координатной прямой точкой. Полож.числам соответствует полупрямая справа от числа 0, отрицательным- полупрямая слева от 0. Мн.R действительных чисел и множество точек координатной прямой находятся во взаимно однозначном соответствии друг с другом, т.е.каждому действительному числу х соответствует единственная точка координатной прямой, а каждой точке координатной прямой соответствует одно и только одно действительное число. Числа х и –х, где х R+, называются противоположными, если на координатной прямой им соответствуют точки, симметричные относительно точки О. Число, противоположное числу –х, есть число х, т.е. –(-х)=х. Расстояние от начала отсчёта до точки с координатной х называется модулем числа х и обозначается . Алгебраическое определение модуля действительного числа:

|х|

Например, |х| =5 означает, что х1=5 или х2=-5, т.к.расстояние от начала отсчёта до точек х1 и х2 равно 5. Геометрическое определение модуля действительного числа можно использовать при решении неравенств, содержащих переменную под знаком абсолютной величины. Например, решением неравенства |х| 5 будет отрезок (-5;5), т.к.расстояние от начала отсчёта точки О до точек этого отрезка меньше 5. П: решить неравенство: |х-3| 5. Исходя из геометрического определения модуля |х-3| есть расстояние от числа 3 до точек с координатами х.Это расстояние должно быть меньше 5. Устанавливаем границы искомого отрезка, ими яв-ся числа -2 и 8. Все числа отрезка (-2;8) удовлетворяют исходному неравенству, т.к.расстояние от числа 3 до любого из чисел найденного отрезка меньше 5.

источник

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

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

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

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

m ⊥ n . <\displaystyle m\perp 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)=9\cdot 11=99>.
  • Вероятность того, что любые k <\displaystyle k>случайным образом выбранных положительных целых чисел будут взаимно просты, равна 1 ζ ( k ) <\displaystyle <\dfrac <1><\zeta (k)>>>, в том смысле, что при N → ∞ <\displaystyle N\to \infty >вероятность того, что k <\displaystyle k>положительных целых чисел, меньших, чем N <\displaystyle <\textstyle >>(и выбранных случайным образом) будут взаимно простыми, стремится к 1 ζ ( k ) <\displaystyle <\dfrac <1><\zeta (k)>>>. Здесь ζ ( k ) <\displaystyle \zeta (k)>— это дзета-функция Римана.
  • Дробь является несократимой тогда и только тогда, когда числитель и знаменатель взаимно просты.

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

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

источник

Adblock
detector