Какие числа не взаимно простые. Взаимно простые числа
Определение1 . Целые числа а 1 ,а 2 ,…,a k называются взаимно-простыми, если (а 1 ,а 2 ,…,a k) =1
Определение 2. Целые числа а 1 ,а 2 ,…,a k называются попарно взаимно-простыми, если i,s (i, s = 1, 2, .. , к, is, (а i , а s) =1).
Если числа удовлетворяют определению 2, то они удовлетворяют и определению 1. Обратное утверждение в общем случае неверно, например: (15, 21, 19)= 1, но (15, 21) = 3
Теорема (критерий взаимной простоты)
(а, b) = 1 <=> х, у Z: ах + by = 1
Доказательство:
Докажем необходимость. Пусть (а, b) = 1. Выше мы показали, что если d=(a,b), то х, y Z: d = ax +by.
Т.к. в этом случае d =1, то будут х, y Z (определяемые из алгоритма Евклида): 1 = ах + bу.
Достаточность. Пусть (*) ах + by = 1, докажем, что (а, b)=1. Предположим, что (a, b) = d, тогда в левой части равенства (*)
(a / d) & (b /d) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.
§4. Нок целых чисел и его свойства.
Определение 1. Общим кратным конечного множества целых чисел а 1 ,а 2 ,…,a k , отличных от нуля, называют целое число m, которое делится на все числа a i (i=l, 2,…, к)
Определение 2. Целое число (m) называется наименьшим общим кратным чисел а 1 ,а 2 ,…,a k , отличных от нуля, если:
1 m - является их общим кратным;
2 (m) делит любое другое общее кратное этих чисел.
Обозначение: m = НОК (а 1 ,а 2 ,…,a k) или m = [а 1 ,а 2 ,…,a k ]
Пример. Даны числа: 2, 3, 4, 6, 12.
Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.
НОК определяется однозначно с точностью до порядка следования сомножителей. Действительно, если предположить, что m 1 = [а, b] &m 2 = (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Между наименьшим общим кратным и наибольшим общим делителем двух целых чисел существует зависимость, которая выражается формулой: [а, b] = ab/(а, b) (выведите ее самостоятельно)
Эта связь позволяет утверждать, что для любой пары целых чисел, отличных от нуля, существует их наименьшее общее кратное. Действительно, (а, b) – всегда можно однозначно вывести из алгоритма Евклида и по определению (а, b) 0, тогда дробь ab/(а, b) 0 и будет определена однозначно.
Наиболее просто НОК двух целых чисел вычисляется в том случае, когда (а,b)= 1, тогда [а, b] = ab/1 = а b
Например, = 215/1 = 105, т. к. (21, 5) = 1.
§5. Простые числа и их свойства.
Определение 1. Натуральное число (р) называется простым, если р > 1 и не имеет положит. делителей, отличных от 1 и р.
Определение 2. Натуральное число а >1, имеющее кроме 1 и самого себя другие положительные делители, называется составным.
Из этих определений следует, что множество натуральных чисел можно разбить на три класса:
а) составные числа;
б) простые числа;
в) единица.
Если
а - составное, то а = nq,
где 1 Задача
1.
Доказать, что если aZ
и р - простое число, то (а, р) = 1 v
(a
/ р) Доказательство.
Пусть
d
= (а, р) =>
(a
/d)
& (р /d),
т.к. р - простое число, то оно имеет два
делителя 1 и р. Если (а, р) = 1, то а и р
взаимно просты, если (а, р) = р, то (а/р). Задача
2.
Если произведение нескольких сомножителей
делится на р, то по крайней мере один из
сомножителей делится на р. Решение.
Пусть
произведение (а 1 ,а 2 ,...,
а k)/р,
если все a i
не будут делиться на р, тогда и произведение
будет взаимно просто с р, следовательно,
какой-то сомножитель делится на р. Задача
3.
Доказать, что наименьший отличный от 1
делитель целого числа а>1, есть число
простое. Доказательство.
Пусть
aZ
и а - составное число (если а = р, то
утверждение доказано), тогда а = a 1 q. Пусть
q
- наименьший делитель, покажем, что он
будет простым числом. Если предположить,
что q
- составное число, тогда q
= q 1 k
и а = a 1 q 1 k,
т.к. q 1 Задача
4.
Доказать, что наименьший простой
делитель (р) натурального числа (n)
не превосходит n
. Доказательство.
Пусть
n
= рn 1 ,
причем р < n 1
и р - простое. Тогда n
р 2
=> р<n
. Из
этого утверждения следует, что если
натуральное число (n)
не делится ни на одно простое число р
n
, то n
– простое, в противном случае оно будет
составным. Пример
1
.
Выяснить, будет ли число 137 простым?
11 <137
<12. Выписываем
простые делители, не превосходящие
137:
2, 3, 5, 7, 11. Проверяем, что 137 не делится на
2, на 3, на 5, на 7, на 11. Следовательно, число
137 – простое. Теорема
Евклида
.
Множество простых чисел бесконечно. Доказательство.
Предположим
противное, пусть p 1 ,p 2 ,...,
p k
все
простые числа, где p 1
= 2, а p k
– самое
большое простое число. Составим
натуральное число
=
p 1 p 2
...
p к
+1,
т.к.
p i
, то оно должно быть составным, тогда
его наименьший делитель будет простым
(см. задачу 3). Однако
не делится ни на p 1
, ни на
p 2
,…, ни
на p k
, т.к. 1
не делится на любое p I . Следовательно,
наше предположение о конечности множества
простых чисел было неверно. Однако существует
теорема, которая утверждает, что простые
числа составляют лишь небольшую часть
чисел натурального ряда. Теорема
об интервалах.
В натуральном ряду существует сколь
угодно длинные интервалы, не содержащие
ни одного простого числа. Доказательство.
Возьмём
произвольное натуральное число (n)
и составим последовательность натуральных
чисел (n+1)!+2,
n+1)!+3,…,(n+1)!+(n+1). В
этой последовательности каждое
последующее число на 1 больше предыдущего,
все эти числа составные, т.к. каждое
имеет более двух делителей (например,
первое число делится на 1, на 2 и само на
себя). При n→∞
мы получим сколь угодно длинный интервал,
состоящий только из составных чисел. Теорема Евклида
и теорема об интервалах свидетельствуют
о сложном характере распределения
простых чисел в натуральном ряду. Основная теорема
арифметики
Любое
натуральное число n>1
может быть представлено единственным
образом в виде произведения простых
чисел, с точностью до порядка следования
сомножителей. Доказательство.
Докажем возможность
представления: Пусть
nN
и n>1,
если n
– простое число, то n
= p
и теорема доказана. Если n
– составное, то наименьший его делитель
будет числом простым и n
= p 1 n 1 ,
где n 1 Далее
рассуждаем аналогично. Если n 1
простое число, то теорема доказана, если
n 1
составное число, то n 1
= p 2 n 2
, где n 2
< n 1
и тогда n
= p 1 p 2 n 2
. На каком-то шаге получим n
= p 1 p 2
…p n
, где все p i
- простые числа. Докажем единственность
разложения: Предположим,
что для числа (n)
есть два различных представления: n
= p 1 p 2
…p k ,
n
= q 1 q 2
…q n
и n>k. Тогда
получим, что p 1 p 2
…p k
= q 1 q 2
…q n
(1). Левая
часть равенства (1) делится на p 1 ,
тогда по свойству простых чисел (см.
задача 2), по крайней мере, один из
сомножителей правой части должен
делиться на p 1 . Пусть
(q 1 /p 1)
=> (q 1 =p 1).
Разделив обе части равенства (1) на p 1 ,
получим равенство p 2 p 3
…p k
= q 2 q 3
…q n
. Повторяя
прежнее рассуждение ещё (k-1)
раз, мы получим равенство 1 = q k +1 q k +2
…q n
, т.к. все
q i
>1, то это
равенство невозможно. Следовательно,
в обеих разложениях число сомножителей
одинаково (k=n)
и сами сомножители одинаковы. Замечание.
В разложении числа (n)
на простые сомножители некоторые из
них могут повторяться. Обозначая буквами
1 , 2 ,…, k
кратность
их вхождения в (n),
получим так называемое каноническое
разложение числа (n):
Пример
2.
Каноническое
разложение числа 588000 = 2 5 35 3 7 2 Следствие
1.
Если
Пример
3.
Все делители
числа 720 = 2 4 3 2 5
получим, если в выражении
Искомые делители
будут равны: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; 9; 18; 36;
72; 144; 5; 10; 20; 40; 80; 15; 30; 60; 120; 240; 45; 90; 180; 360;
720. Следствие
2.
Если
P 1 1
p 2 2
…p k k
,
где
i
= max( I ,
i). Пример
4.
Найти
НОД(a,
b)
и НОК(a,
b),
используя каноническое разложение,
если (24,
42) = 23
= 6 Ключевые слова: теория чисел, лекции, взаємно прості числа.
Определение.
Целые числа 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 . Рассуждаем: Р
Учебники математики порой сложны для восприятия. Сухой и четкий язык авторов не всегда доступен для понимания. Да и темы там всегда взаимосвязанные, взаимовытекающие. Для освоения одной темы приходится поднимать ряд предыдущих, а порой и перелистывать весь учебник. Сложно? Да. А давайте рискнем обойти эти сложности и попробуем найти к теме не совсем стандартный подход. Сделаем эдакий экскурс в страну чисел. Определение, однако, мы все-таки оставим прежним, ибо правила математики отменить нельзя. Итак, взаимно простые числа — числа натуральные, с общим делителем, равным единице. Это понятно? Вполне. Для более наглядного примера давайте возьмем числа 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 долларов). Что такое взаимно простые числа? Определение взаимно простых чисел: Взаимно простые числа - это целые числа, у которых нет общих делителей, кроме единицы. Пример взаимно простых чисел: У 2 и 3 нет иных общих делителей кроме единицы. Ещё пример взаимно простых чисел: У 3 и 7 нет иных общих делителей кроме едининицы. Другой пример взаимно простых чисел: У 11 и 13 нет иных общих делителей кроме едининицы. Теперь мы можем ответить на вопрос, что значит взаимно простые числа. Что значит взаимно простые числа? Это целые числа, у которых нет общих делителей, кроме единицы. Каждая из этих пар есть два взаимно простых числа. 11 и 15 Общие делители взаимно простых чисел - это только единица, что следует из определения взаимно простых чисел. Наибольший общий делитель взаимно простых чисел - это единица, что следует из определения взаимно простых чисел. Являются ли взаимно простыми числа 3 и 13? Да, ведь у них нет общих делителей, кроме единицы. Являются ли взаимно простыми числа 3 и 12? Нет, ведь у них общими делителями являются 1 и 3. А по определению взаимно простых чисел общим делителем должна быть только единица. Являются ли взаимно простыми числа 3 и 108? Нет, ведь у них общими делителями являются 1 и 3. А по определению взаимно простых чисел общим делителем должна быть только единица. Являются ли взаимно простыми числа 108 и 5? Да, ведь у них нет общих делителей, кроме единицы. В этом статье мы расскажем о том, что такое взаимно простые числа. В первом пункте сформулируем определения для двух, трех и более взаимно простых чисел, приведем несколько примеров и покажем, в каких случаях два числа можно считать простыми по отношению друг к другу. После этого перейдем к формулировке основных свойств и их доказательствам. В последнем пункте мы поговорим о связанном понятии – попарно простых числах. Yandex.RTB R-A-339285-1
Взаимно простыми могут быть как два целых числа, так и их большее количество. Для начала введем определение для двух чисел, для чего нам понадобится понятие их наибольшего общего делителя. Если нужно, повторите материал, посвященный ему. Определение 1
Взаимно простыми будут два таких числа 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 , на что указывает соответствующий признак делимости. На практике довольно часто приходится определять взаимную простоту двух целых чисел. Выяснение этого можно свести к поиску наибольшего общего делителя и сравнению его с единицей. Также удобно пользоваться таблицей простых чисел, чтобы не производить лишних вычислений: если одно из заданных чисел есть в этой таблице, значит, оно делится только на единицу и само на себя. Разберем решение подобной задачи. Пример 1
Условие:
выясните, являются ли взаимно простыми числа 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 , то данные числа будут взаимно простыми. Как мы уже говорили раньше, определение таких чисел можно распространить и на случаи, когда у нас есть не два числа, а больше. Определение 2
Взаимно простыми целые числа 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 . Обычно взаимная простота чисел не является очевидной с первого взгляда, этот факт нуждается в доказательстве. Чтобы выяснить, будут ли некоторые числа взаимно простыми, нужно найти их наибольший общий делитель и сделать вывод на основании его сравнения с единицей. Пример 2
Условие:
определите, являются ли числа 331 , 463 и 733 взаимно простыми. Решение
Сверимся с таблицей простых чисел и определим, что все три этих числа в ней есть. Тогда их общим делителем может быть только единица. Ответ:
все эти числа будут взаимно простыми по отношению друг к другу. Пример 3
Условие:
приведите доказательство того, что числа − 14 , 105 , − 2 107 и − 91 не являются взаимно простыми. Решение
Начнем с выявления их наибольшего общего делителя, после чего убедимся, что он не равен 1 . Поскольку у отрицательных чисел те же делители, что и у соответствующих положительных, то НОД (− 14 , 105 , 2 107 , − 91) = НОД (14 , 105 , 2 107 , 91) . Согласно правилам, которые мы привели в статье о нахождении наибольшего общего делителя, в данном случае НОД будет равен семи. Ответ:
семь больше единицы, значит, взаимно простыми эти числа не являются. Такие числа имеют некоторые практически важные свойства. Перечислим их по порядку и докажем. Определение 3
Если разделить целые числа a и b на число, соответствующее их наибольшему общему делителю, мы получим взаимно простые числа. Иначе говоря, a: НОД (a , b) и b: НОД (a , b) будут взаимно простыми. Это свойство мы уже доказывали. Доказательство можно посмотреть в статье о свойствах наибольшего общего делителя. Благодаря ему мы можем определять пары взаимно простых чисел: достаточно лишь взять два любых целых числа и выполнить деление на НОД. В итоге мы должны получить взаимно простые числа. Определение 4
Необходимым и достаточным условием взаимной простоты чисел a и b является существование таких целых чисел u 0
и v 0
, при которых равенство a · u 0 + b · v 0 = 1
будет верным. Доказательство 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 . Определение 5
Если два целых числа a и b являются взаимно простыми, то НОД (a · c , b) = НОД (c , b) . Доказательство 2
Докажем, что НОД (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) взаимно делят друг друга, значит, они являются равными. Определение 6
Если числа из последовательности 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
– взаимно простые. Доказательство 3
Согласно предыдущему свойству, мы можем записать равенства следующего вида: НОД (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
Это все свойства взаимно простых чисел, о которых бы мы хотели вам рассказать. Зная, что из себя представляют взаимно простые числа, мы можем сформулировать определение попарно простых чисел. Определение 7
Попарно простые числа
– это последовательность целых чисел 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 . В случае с простыми числами понятия взаимной и попарной простоты будут совпадать. Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
тогда все делители числа (n)
имеют вид:
где 0 i i
(i
= 1, 2,…,k).
вместо 1 ,
2 ,
3
, независимо друг от друга, будем
подставлять значения: 1 =0,
1, 2, 3, 4, 2 =0,
1, 2, 3
= 0, 1.
и
то
(a, b) = p 1 1
p 2 2
…p k k ,
где
i
= min( I ,
i)
Для чего нам такие знания? Причин достаточно.Взаимно простые числа определение
Взаимно простые числа примеры
Два взаимно простых числа
15 и 16
16 и 23Общие делители взаимно простых чисел
Наибольший общий делитель взаимно простых чисел
Являются ли взаимно простыми числа?
Что такое взаимно простые числа
Основные свойства взаимно простых чисел
Понятие попарно простых чисел