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

Докажите что числа: a)260 и 117 не взаимно простые ; б) 945 и 544 взаимно простые.

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.

1. Дано действительное число – цена 1 кг конфет. Вывести стоимость 0,5; 1; 1,5 … 10 кг конфет. (Подсказка – используем цикл WHILE).

Программа должна иметь следующий вид:

Компьютер запрашивает стоимость одного килограмма конфет.

Пользователь вводит стоимость одного килограмма конфет, и компьютер выводит на экран:

§1.4. Взаимно простые числа. Основная теорема арифметики

Определение 1.4.1. Целые числа называются взаимно простыми, если .

Такие числа не имеют общих простых делителей. Развитием теоремы 1.2.3 и следствия из нее является следующая теорема.

Теорема 1.4.1 (критерий взаимной простоты). Целые числа взаимно просты тогда и только тогда, когда существуют такие целые числа , что

.

Необходимость. , из соотношения Безу для НОД следует, что , такие, что .

Достаточность. Пусть , такие, что . Если , то d | 1 (в силу свойства 5 делимости целых чисел), следовательно, d = 1.

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

1.  .

Необходимость. Согласно следствию из теоремы 1.2.3 , такие, что , следовательно, , зна-чит, по теореме 1.4.1.

Достаточность. />, следовательно, , такие, что (согласно теореме 1.4.1), откуда d = u₁a₁ +…+ + u_na_n. Значит, по свойству 5 делимости целых чисел, а поскольку , то по определению НОД, следовательно, .

2. с | ab  (c, a) = 1  с | b.

При b  0  t, u, v  Z, такие, что ab = ct  cu + av = 1  cub + ctv = b   с | b по свойству 5 делимости целых чисел. При b = 0 доказательство очевидно согласно свойству 1 делимости целых чисел.

3.  .

Необходимость.

где . Значит, согласно теореме 1.4.1.

Достаточность. Пусть . Если предположить, что или , то согласно свойству 3 делимости целых чисел и определению НОД получим, что либо . Это противоречит тому, что . Значит,  .

4. Следствие из свойства 3. Простое число p делит произведение , k  N, тогда и только тогда, когда , 1  i  k, со свойством .

Необходимость. Если с указанным свойством, то по свойству 1 простых чисел , значит, по свойству 3 взаимно простых чисел, следовательно, снова по свойству 1 простых чисел, что приводит к противоречию. Итак, , 1  i  k, со свойством .

Достаточность. Если , 1  i  k, со свойством , то по свойству 3 делимости целых чисел.

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

Теорема 1.4.2 (основная теорема арифметики). Всякое натуральное число n > 1 однозначно раскладывается в произведение простых чисел с точностью до порядка следования множителей:

, . (1.4.1)

n = 2 – база индукции. Предположим, что утверждение верно для .

Для простого числа n доказательство очевидно, s = 1. Пусть – составное число, . Воспользуемся предположением индукции и разложим на простые множители и />, тем самым в произведение простых чисел будет разложено и n.

Пусть и , s, t  N, – два разложения числа n на простые множители. Тогда, воспользовавшись свойством 4 взаимно простых чисел и свойством 1 простых чисел и последовательно сокращая обе части равенства = на , приходим к выводу, что s = t и с точностью до порядка следования множителей , . Таким образом, разложение (1.4.1) числа n однозначно с точностью до порядка следования множителей.

Определение 1.4.2. Если в равенстве (1.4.1) собрать одинаковые множители в степени, то получим каноническое разложение натурального числа n > 1: , где , , при i  j. Если z – целое, не равное 0, 1 число, то – каноническое разложение .

Пример 1.4.1. Найдем разложения вида (1.4.1) и канонические разложения целых чисел.

1. – 484 = – 2  242 = – 2  2  121 = – 2  2  11  11 = – 2 2  11 2 .

2. 2 12 – 1 = 4095 = 3  1365 = 3  3  455 = 3  3  5  91 = 3  3  5  7  13 = = 3 2  5  7  13.

По каноническому разложению целых чисел легко находятся их НОД и НОК, решаются иные задачи.

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

, , , , ,

где p₁,…, p_t – простые числа, входящие во все разложения , , причем в случае отсутствия множителя p_j в разложении полагается _ij = 0. Тогда, исходя из определений, получаем следующие формулы для канонических разложений НОД и НОК чисел :

, где , ,

, где , .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разложение на простые множители

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

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

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

$180=2^2\cdot 3^2\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$.

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

$195=3\cdot 5\cdot 13$

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

$НОД \ (195;336) =3\cdot 5=15$

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

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

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

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

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

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

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

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