Взаимно простые числа: определение, примеры и свойства
Эта статья – экскурс в мир математики и взаимно простых чисел. Но не стоит их путать с «простыми». Далее вы узнаете почему взаимно простые числа являются простыми, чем они отличаются и для чего они нужны. Будут рассмотрены все характеристики и особенности взаимно простых чисел. Все свойства и особые случаи будут рассмотрены на наглядных примерах. Шаг за шагом мы подойдем к доказательствам и рассмотрим такую вещь, как попарно простые числа.
Что такое взаимно простые числа?
Взаимно простым числом называют целое число, которое имеет с другим числом наибольший общий делитель – 1 (единицу).
Возьмем 2 простых числа и определим их, как a и b. Взаимно простыми будут те числа, которые имеют 1, как наибольший общий делитель (НОД). (a, b) = 1
У двух взаимно простых чисел будет один положительный общий делитель. И делитель будет равен 1. Только два таких числа имеют два общих делителя 1 и -1.
Пример 1:
Простым примером взаимно простых будут числа 5 и 11. Почему? Давайте посмотрим на делители этих чисел: 5 делится на 5 и на 1, а число 11 можно разделить на 11 и на 1 (без остатка). Общим положительным делителем этих двух чисел будет единица. Единица – самый большой общий делитель двух чисел – значит, что они будут взаимно простые.
Но не только простые числа могут быть взаимно простыми по отношению друг к другу. Условие взаимной простоты образуется и между составными числами.
Составное число – число, делители которого отличаются от самого числа и единицы).
Ситуаций, где в паре чисел одно является простым, а второе составным, или оба являются составными – не редкость. И мы научимся с ними работать.
Пример 2:
Возьмем для примера два числа: -9 и 8. Мы утверждаем, что они образуют взаимно простую пару. Так ли это? Давайте проверим. Для того, чтобы это доказать (или опровергнуть) нужно найти их общий делитель. Распишем делители каждого из чисел в ряд:
Для числа 8 делителями будут: ±1, ±2, ±4, ±8;
Для числа 9 делителями будут: ±1, ±3, ±9.
Выбираем из рядов делителей общий и самый большой: ±1. Из этого следует, что, если наибольший общий делитель (НОД) чисел 8 и -9 это единица, то они взаимно простые друг к другу.
А вот числа 45 и 500 не будут таковыми. Почему? Помимо единицы, они имеют еще один общий делитель 5, и он больше единицы (вспоминаем правило про наибольший общий делитель). 5 больше 1, значит о взаимной простоте чисел не может быть и речи.
Аналогичная ситуация с числами 201 и 3. Если расписать все из общие делители, то там будет число 3. А 3 больше 1, значит и в этой ситуации нет взаимной простоты между числами.
Как показывает практика, решение задач на определение взаимной простоты встречаются часто и не только в школьных учебниках. Вся их суть сводится к одному: поиск наибольшего общего делителя этих чисел и сравнение его с единицей. Расписывать все делители будет очень проблематично, в некоторых случаях. Например, число 234 567. Для упрощения задачи есть несколько вариантов:
- Использование таблицы простых чисел. Если одно из чисел в ней есть, то оно простое и делится на себя и единицу;
- Алгоритм Евклида.
Разберем решение таковой задачи на примере.
Нет времени решать самому?
Наши эксперты помогут!
Контрольная
| от 300 ₽ |
Реферат
| от 500 ₽ |
Курсовая
| от 1 000 ₽ |
Геометрический алгоритм Евклида
Данный алгоритм часто применяется для решения задач по нахождению наибольшего общего делителя двух чисел (целых). Алгоритм работает следующим образом:
Возьмем 2 целых числа и обозначим их как a и b. Представим числа в виде отрезков. Каждый из них имеет свое числовое значение.
- Из большего отрезка нужно вычесть меньший;
- Больший отрезок заменим полученной разностью величин;
- Продолжаем вычитать из большего отрезка меньший, пока они не станут равны;
- Процедуру вычитания проводим до тех пор, пока отрезки не станут равны.
Если в итоге получаем отрезки равной величины, то значит, что они соизмеримы. И последний полученный результат — это и есть показатель их наибольшей общей меры.
Если общей меры отрезков нет, то процесс будет продолжаться бесконечно.
Метод использования алгоритма Евклида. Найдем НОД двух чисел 1071 и 462. Представим и в виде буквенных обозначений. Пусть, a = 1071, b = 462.
Из 1071 вычтем 462 кратное число раз. Это можно сделать 2 раза. Количество раз, которое можно вычесть наименьшее число из большего обозначим буквой q.
1071 – 462 ⋅ 2 = 147
Из наименьшей величины (все, как в алгоритме Евклида) вычтем кратное число раз разность.
462 – 174 ⋅ 3 = 21
И снова проделываем аналогичное вычисление.
147 – 21 ⋅ 7 = 0
Последний остаток в данном примере = 21. Следовательно, НОД для чисел 1071 и 462 =21. Делаем вывод, что 21 > 1, значит данные числа не будут взаимно простыми.
Теперь можно попробовать применить данную формулу на практике.
Условие: нужно выяснить, являются ли числа 275 и 84 взаимно простыми или нет.
И то, и то число, точно имеют больше 1 делителя. Сразу сказать, что они взаимно простые нельзя. Для вычисления НОД применим алгоритм Евклида:
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, то взаимная простота чисел доказана.
Если есть числовой ряд с большим количеством чисел и у всех у них наибольшим делителем является единица, то они будут проявлять свойство взаимной простоты по отношению друг к другу.
Количество чисел не имеет значение. Их может быть сколько угодно много. Главное – наибольший общий делитель – единица. Для наглядности, возьмем ряд чисел: 2, 3, 11, 19, 667. Они все делятся только сами на себя и на 1. Из это следует, что их свойство взаимной простоты доказано.
Условие: определить наличие взаимной простоты у чисел 331, 463, 733 или опровергнуть ее.
Решение:
Используем для решения таблицу простых чисел. Проверим данные числа и таблицу. Да, в таблице можно встретить
их все. Это значит, что общим делителем чисел будет 1.
Ответ: все числа находятся в таблице простых чисел. Их наибольший делить -1. Значит все они взаимно
простые друг к другу.
Докажите, что следующие числа не являются взаимно простыми (105, — 14, — 2007, — 91).
Решение:
- Нужно найти общий наибольший делитель. Это можно сделать любым удобным способом;
- Вспоминаем, что отрицательные числа имеют те же делители, что и положительные.
- НОД для всех чисел будет = 7.
Ответ: 7 больше 1. Значит, что числа не будут являться взаимно простыми.
Свойства взаимно простых чисел и их доказательства
У таких чисел есть ряд свойств и особенностей. Давайте посмотрим на них, разберем на практике и докажем их правдивость.
Свойство — 1
Если разделить числа a и b на их общий делитель, то полученные числа будут взаимно простыми.
a : НОД (a, b) и b: НОД (a, b) будут взаимно простыми.
Свойство — 2
Условие взаимной простоты чисел – существование целых чисел \[\mathrm{U}_{0}\] и \[\mathrm{V}_{0}\] при значениях которых, следующее равенство будет верно:
\[a \cdot u_{0}+b \cdot v_{0}=1\]. Эта формула называется – соотношение Безу.
Доказательство свойства 2:
Пусть данное равенство будет верно a · u0 + b · v0 = 1. Так как, НОД чисел (a, b) делит и одно и второе, то исходя из свойств делимости НОД может делить сумму чисел a · u0 + b · v0. Значит он может делить их и на 1. Такое условие будет возможно только в том случае, если НОД (a, b) будет равен 1. Из этого следует, что НОД = 1. Что и требовалось доказать.
Свойство 3
Если число a и число b будут взаимно простыми, а их произведение обозначим, как c. В
такой ситуации, a · с будет делиться на b. Из этого следует, что и c будет делиться на
b.
Так, как числа a, b являются взаимно простыми, то исходя из Свойства 2, можно получить
следующее равенство: \[a u_{0}+b v_{0}=1\].
Если каждую часть уравнения перемножить на c, получим следующее:
\[\mathrm{acu}_{0}+\mathrm{bcv}_{0}=\mathrm{c}\].
Слагаемое суммы \[\mathrm{acu}_{0}+\mathrm{bc} \mathrm{v}_{0}\] можно разделить на число b. Так как,
число ac делится на b. Второе слагаемое тоже будет делиться на число b. Почему? Потому
что,
один из множителей будет равен числу b.
Вывод: вся сумма будет делиться на число b, так как,
\[\mathrm{acu}_{0}+\mathrm{bcv}_{0}=\mathrm{c}\].
Следовательно, c будет делиться на b.
Свойство 4
Если числа a, b являются взаимно простыми, то и НОД (ac, b) будет равен НОД (c, b)
Наибольший общий делитель (ac, b) делит и ac и число b.
Следовательно, он будет делить и произведение чисел bc. Это значит, что НОД (ac, b) делит и ac
и bc. Исходя
их свойств НОД, он будет делить и НОД чисел (ac, bc), который по своим свойствам равен числу c.
Отсюда следует, что наибольший общий делитель чисел (ac, b) делит и b и c, а значит, что и
делит НОД (c, b).
Свойство 5
Возьмём числовую последовательность \[a_{1}, a_{2}, \ldots, a_{k}\]. В ней все числа взаимно простые с каждым
из числовой последовательности \[b_{1}, b_{2}, \ldots, b_{m}\] (Числа k и m – натуральные), то
произведения \[a_{1} \cdot a_{2} \cdot \ldots a_{k}\] и \[b_{1} \cdot b_{2} \cdot \ldots b_{m}\] будут взаимно простыми.
Если, \[a_{1}=a_{2}=\ldots=a_{k}=a\] и \[b_{1}=b_{2}=\ldots=b_{m}=b\], то \[a_{k}\] и \[\mathrm{b}_{\mathrm{m}}\] являются взаимно простыми числами.
Попарно простые числа
Так как, мы уже знаем, что такое взаимно простые числа, то понять, что значит взаимно простые числа попарны будет проще.
Попарно простые числа – последовательность целых чисел (a 1, a 2, … , a k a1, a2, …, ak), где каждое следующее число будет взаимно простым по отношению ко всем остальным.
Пример 1:
Возьмем числовой ряд 14, 9, 17, 25. Все пары, которые могут быть составлены из этих чисел будут взаимно простыми: 17 – 25, 9 – 25, 14 – 9, 14 – 17, 9 – 17, 14 – 25.
Главным условием для попарных чисел является условие взаимной простоты. При этом, взаимно простые числа не всегда будут попарно простыми.
Пример 2:
В числовой последовательности 8, 16, 5, 15 числа не будут попарными. Почему? Числа 16 и 8 – не являются взаимно простыми.
Возьмем совокупность и некоторое число простых чисел, особенность таковых в том, что они в любом случае будут, как попарно, так и взаимно простыми. Если рассматривать ситуацию с простыми числами, то свойства взаимной и попарной простоты совпадают.
