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

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

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

Пример 1

Найти делители числа $6$.

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

Ответ: $1,2,3,6$.

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

Определение 2

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

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

Замечание 1

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

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

Определение 3

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

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

Определение 4

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

Пример 2

$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^{n1}_1\cdot p^{n2}_2\cdot \dots \dots ..\cdot p^{nk}_k$

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

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

Пример 3

Найти наибольший общий делитель чисел $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.Полученное число и будет искомым наибольшим общим делителем.

Пример 4

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

Пример 5

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

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

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

$НОД \ (39;112)=1$

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

Пример 6

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

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

$883=1\cdot 883$

$997=1\cdot 997$

$НОД \ (883;997)=1$

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

Ключевые слова: теория чисел, лекции, взаємно прості числа.

Определение. Целые числа a и b называются взаимно простыми, если (a , b) = 1.

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

Пусть X = { x n | n = 1, 2,...} - произвольная строго возрастающая последовательность натуральных чисел (или, если угодно, X - произвольное подмножество натуральных чисел, упорядоченное естественным образом). Обозначим через ξ(N; X) число членов последовательности X, не превосходящих N .

Определение. Число называется (верхней асимптотической) плотностью последовательности X = { x n | n = 1, 2,...} в множестве N .

Пример 1. Пусть x n = 2n , где n пробегает N , - последовательность всех четных чисел. Очевидно, что

Между прочим, это хорошо согласуется с нашими интуитивными представлениями о том, что четных чисел - половина.

Пример 2. Пусть x n =2 n , где n пробегает N , - геометрическая прогрессия. Интуитивно ясно, что таких чисел в натуральном ряду мало, ибо чем "дальше в лес" по натуральному ряду, тем реже встречается степень двойки. Понятие плотности подтверждает это ощущение: ξ (2 k ; { x n }) = k , и, легко проверить, что

Плотность - это вероятность наугад вытащить из натурального ряда число, принадлежащее заданной последовательности.

Аналогично определению плотности последовательности, можно дать определение плотности множества пар натуральных чисел. Пусть имеется произвольное множество Х упорядоченных пар натуральных чисел. Обозначим через ξ (N ; X) число пар из множества Х, каждая компонента которых не превосходит N . Полезно представить себе пары чисел из множества Х как координаты точек на координатной плоскости, тогда ξ (N ; X) есть просто число точек множества Х, попавших в квадрат {(x , y) | 0 < x ≤ N ; 0 < y ≤ N }.

Определение. Число

называется (верхней асимптотической) плотностью множества пар Х в множестве N 2 .

Пример 3. Пусть Х - множество всех пар натуральных чисел, у которых первая компонента строго больше второй. Множеству Х соответствуют точки первой четверти координатной плоскости, лежащие под биссектрисой y = x . Плотность такого множества легко подсчитать:

Пусть X - множество всех упорядоченных пар (u , v) натуральных чисел таких, что (u , v) = 1, т.е. множество всех пар взаимно простых чисел.

Теорема (Чезаро). Вероятность выбрать из N пару взаимно простых чисел равна 6/π 2 , точнее Доказательство. Предположим сразу, что существует вероятность p того, что случайно выбранные натуральные числа а и b взаимно просты. Пусть d ∈ N . Через P { S } обозначим, как обычно, вероятность события S . Рассуждаем: Р

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

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

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

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

Кроме ±1.

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

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

Обозначения

Для указания взаимной простоты чисел m {\displaystyle m} и n {\displaystyle n} используется обозначение :

m ⊥ n . {\displaystyle m\perp n.}

Однако не все математики признают и используют это обозначение. Чаще всего используется словесная формулировка или эквивалентная запись 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 c {\displaystyle bc} , и a {\displaystyle a} взаимно просто с b {\displaystyle b} , то a {\displaystyle a} - делитель c {\displaystyle c} .
• Если числа a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} - попарно взаимно простые числа, то НОК (a 1 , … , a n) = | a 1 ⋅ … ⋅ a n | {\displaystyle (a_{1},\ldots ,a_{n})=|a_{1}\cdot \ldots \cdot a_{n}|} . Например, НОК (9 , 11) = 9 ⋅ 11 = 99 {\displaystyle (9,11)=9\cdot 11=99} .
• Вероятность того, что любые k {\displaystyle k} случайным образом выбранных положительных целых чисел будут взаимно просты, равна , в том смысле, что при N → ∞ {\displaystyle N\to \infty } вероятность того, что k {\displaystyle k} положительных целых чисел, меньших, чем N {\displaystyle {\textstyle {N}}} (и выбранных случайным образом) будут взаимно простыми, стремится к 1 ζ (k) {\displaystyle {\dfrac {1}{\zeta (k)}}} . Здесь ζ (k) {\displaystyle \zeta (k)} - это

Учебники математики порой сложны для восприятия. Сухой и четкий язык авторов не всегда доступен для понимания. Да и темы там всегда взаимосвязанные, взаимовытекающие. Для освоения одной темы приходится поднимать ряд предыдущих, а порой и перелистывать весь учебник. Сложно? Да. А давайте рискнем обойти эти сложности и попробуем найти к теме не совсем стандартный подход. Сделаем эдакий экскурс в страну чисел. Определение, однако, мы все-таки оставим прежним, ибо правила математики отменить нельзя. Итак, взаимно простые числа — числа натуральные, с общим делителем, равным единице. Это понятно? Вполне.

Для более наглядного примера давайте возьмем числа 6 и 13. И то, и другое — делимы на единицу (взаимно простые). А вот числа 12 и 14 — таковыми не могут являться, поскольку делятся не только на 1, но и на 2. Следующие числа — 21 и 47 тоже не подходят к категории "взаимно простые числа": их можно разделить не только на 1, но еще и на 7.

Обозначают взаимно простые числа так: (а , у) = 1.

Можно сказать даже проще: общий делитель (наибольший) здесь равен единице.
Для чего нам такие знания? Причин достаточно.

Взаимно включены в некоторые системы шифрования. Те, кто работает с шифрами Хилла или с системой подстановок Цезаря, понимают: без этих знаний — никуда. Если вы слышали о генераторах то вряд ли решитесь отрицать: взаимно простые числа используются и там.

Теперь поговорим о способах получения таких простые, как вы понимаете, могут иметь лишь два делителя: они делимы на самих себя и на единицу. Скажем, 11, 7, 5, 3 — числа простые, а вот 9 — нет, ведь это число уже делимо и на 9, и на 3, и на 1.

И если а — число простое, а у - из множества {1, 2, ... а - 1}, то тогда гарантированно (а , у ) = 1, или взаимно простые числа — а и у .

Это, скорее, даже не объяснение, а повторение или подведение итогов только что сказанного.

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

Можно работать путем подбора у > а . Для этого у выбирается так, чтобы число на а не делилось. Для этого число простое умножается на число натуральное и прибавляется (или, напротив, вычитается) величина (допустим, р ), которая меньше а :

у = р а + k

Если, например, а = 71, р = 3, q=10, то, соответственно, у здесь будет равен 713. Возможен и другой подбор, со степенями.

Составные числа, в отличие от взаимно простых, делятся и на себя, и на 1, и на другие числа (тоже без остатка).

Другими словами, (кроме единицы) разбиты на составные и простые.

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

Самое большое простое число найдено доктором-офтальмологом Мартином Новаком, участвовавшим в проекте GIMPS (распределительные вычисления) вместе с другими энтузиастами, которых насчитывалось около 15 тыс. На расчеты ушло шесть долгих лет. Было задействовано два с половиной десятка компьютеров, находящихся в глазной клинике Новака. Результатом титанического труда и упорства явилось число 225964951-1, с записыванием в 7816230-десятичных знаках. Кстати, рекорд самого большого числа был поставлен за полгода до этого открытия. И знаков там было на полмиллиона меньше.

У гения, желающего назвать число, где продолжительность десятичной записи "перепрыгнет" десятимиллионную отметку, есть шанс получить не только всемирную славу, но и 100 000 долларов. Кстати, за число, преодолевшее миллионный рубеж знаков, Наян Хайратвал получил меньшую сумму (50 000 долларов).