Взаимная простота - NiNa.Az

Взаимно простые числа — целые числа, не имеющие никаких общих делителей, кроме ${\displaystyle \pm 1}$. Равносильное определение: целые числа взаимно просты, если их наибольший общий делитель равен ${\displaystyle 1}$.

В «лесу», составленном на координатной плоскости из точек с целочисленными координатами, из начала координат «видны» только «деревья» со взаимно простыми координатами.

Например, взаимно просты числа ${\displaystyle 14}$ и ${\displaystyle 25}$, так как у них нет общих делителей; но числа ${\displaystyle 15}$ и ${\displaystyle 25}$ не взаимно просты, так как у них имеется общий делитель ${\displaystyle 5}$.

Для указания взаимной простоты чисел ${\displaystyle m}$ и ${\displaystyle n}$ иногда используется обозначение ${\displaystyle m\perp n}$ (аналогия с перпендикулярными прямыми, не имеющими общих направлений — взаимно простые числа не имеют общих сомножителей).

Это понятие было введено в книге VII «Начал» Евклида. Для определения того, являются ли два числа взаимно простыми, можно использовать алгоритм Евклида.

Понятие взаимной простоты естественным образом обобщается на любые евклидовы кольца.➤

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

Если в наборе целых чисел любые два числа взаимно просты, то такие числа называются попарно взаимно простыми (или просто попарно простыми). Для двух чисел понятия «взаимно простые» и «попарно простые» совпадают, для более чем двух чисел свойство попарной простоты более сильно, чем ранее определённое свойство взаимной простоты (в совокупности) — попарно простые числа будут и взаимно простыми, но обратное неверно. Примеры:

• ${\displaystyle 8,15}$ — не простые, но взаимно простые.
• ${\displaystyle 6,8,9}$ — взаимно простые (в совокупности) числа, но не попарно простые.
• ${\displaystyle 8,15,49}$ — попарно простые и взаимно простые (в совокупности).

Если числа ${\displaystyle a_{1},\ldots ,a_{n}}$ — попарно простые числа, то:

• их наименьшее общее кратное равно абсолютной величине их произведения: ${\displaystyle |a_{1}\cdot \ldots \cdot a_{n}|}$;
• для любого целого ${\displaystyle b}$ имеет место формула:

${\displaystyle {\text{НОД}}(a_{1}\cdot a_{2}\ldots a_{n},b)={\text{НОД}}(a_{1},b)\cdot {\text{НОД}}(a_{2},b)\cdot \ldots \cdot {\text{НОД}}(a_{n},b)}$, где ${\displaystyle {\text{НОД}}}$ — наибольший общий делитель.

Свойства

Все упомянутые в этом разделе числа подразумеваются целыми, если не оговорено иное.

• Количество натуральных чисел, взаимно простых с натуральным числом ${\displaystyle n}$ и не превосходящих его задаётся функцией Эйлера ${\displaystyle \varphi (n)}$.
• Числа ${\displaystyle a}$ и ${\displaystyle b}$ взаимно просты тогда и только тогда, когда существуют целые ${\displaystyle x}$ и ${\displaystyle y}$ такие, что ${\displaystyle ax+by=1}$ (соотношение Безу). Если натуральные числа ${\displaystyle a}$ и ${\displaystyle b}$ взаимно просты, то числа ${\displaystyle 2^{a}-1}$ и ${\displaystyle 2^{b}-1}$ также взаимно просты, притом верно и обратное.
• (Лемма Евклида) Если ${\displaystyle a}$ — делитель произведения ${\displaystyle bc}$ и ${\displaystyle a}$ взаимно просто с ${\displaystyle b}$, то ${\displaystyle a}$ — делитель ${\displaystyle c}$.
• Если ${\displaystyle d={\text{НОД}}(a,b)}$, то числа ${\displaystyle {\frac {a}{d}}}$ и ${\displaystyle {\frac {b}{d}}}$ взаимно просты.
• Дробь является несократимой тогда и только тогда, когда её числитель и знаменатель взаимно просты.
• Если числа ${\displaystyle a}$ и ${\displaystyle m}$ взаимно просты, то сравнение ${\displaystyle ax\equiv b{\pmod {m}}}$ для любого ${\displaystyle b}$ имеет единственное решение по модулю ${\displaystyle m.}$ В частности, решение сравнения для ${\displaystyle b=1}$ даёт обратный элемент для ${\displaystyle a}$ в кольце вычетов по модулю m. (См. Соотношение Безу)
• Вероятность того, что ${\displaystyle k}$ случайным образом выбранных положительных целых числа будут взаимно просты, равна ${\displaystyle {\dfrac {1}{\zeta (k)}}}$, в том смысле, что при ${\displaystyle N\to \infty }$ вероятность того, что ${\displaystyle k}$ положительных целых чисел, меньших, чем ${\displaystyle {\textstyle {N}}}$ (и выбранных случайным образом), будут взаимно простыми, стремится к ${\displaystyle {\dfrac {1}{\zeta (k)}}}$. Здесь ${\displaystyle \zeta (k)}$ — это дзета-функция Римана.

Таблица взаимной простоты чисел до 30

В каждой клетке стоит наибольший общий делитель её координат, и соответствующие взаимно-простым парам координат единицы выделены тёмным. Из описанного выше свойства следует, что средняя плотность тёмных клеток при расширении таблицы до бесконечности станет равна ${\displaystyle 1/\zeta (2)}$.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2
3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3	1	1	3
4	1	2	1	4	1	2	1	4	1	2	1	4	1	2	1	4	1	2	1	4	1	2	1	4	1	2	1	4	1	2
5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5
6	1	2	3	2	1	6	1	2	3	2	1	6	1	2	3	2	1	6	1	2	3	2	1	6	1	2	3	2	1	6
7	1	1	1	1	1	1	7	1	1	1	1	1	1	7	1	1	1	1	1	1	7	1	1	1	1	1	1	7	1	1
8	1	2	1	4	1	2	1	8	1	2	1	4	1	2	1	8	1	2	1	4	1	2	1	8	1	2	1	4	1	2
9	1	1	3	1	1	3	1	1	9	1	1	3	1	1	3	1	1	9	1	1	3	1	1	3	1	1	9	1	1	3
10	1	2	1	2	5	2	1	2	1	10	1	2	1	2	5	2	1	2	1	10	1	2	1	2	5	2	1	2	1	10
11	1	1	1	1	1	1	1	1	1	1	11	1	1	1	1	1	1	1	1	1	1	11	1	1	1	1	1	1	1	1
12	1	2	3	4	1	6	1	4	3	2	1	12	1	2	3	4	1	6	1	4	3	2	1	12	1	2	3	4	1	6
13	1	1	1	1	1	1	1	1	1	1	1	1	13	1	1	1	1	1	1	1	1	1	1	1	1	13	1	1	1	1
14	1	2	1	2	1	2	7	2	1	2	1	2	1	14	1	2	1	2	1	2	7	2	1	2	1	2	1	14	1	2
15	1	1	3	1	5	3	1	1	3	5	1	3	1	1	15	1	1	3	1	5	3	1	1	3	5	1	3	1	1	15
16	1	2	1	4	1	2	1	8	1	2	1	4	1	2	1	16	1	2	1	4	1	2	1	8	1	2	1	4	1	2
17	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	17	1	1	1	1	1	1	1	1	1	1	1	1	1
18	1	2	3	2	1	6	1	2	9	2	1	6	1	2	3	2	1	18	1	2	3	2	1	6	1	2	9	2	1	6
19	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	19	1	1	1	1	1	1	1	1	1	1	1
20	1	2	1	4	5	2	1	4	1	10	1	4	1	2	5	4	1	2	1	20	1	2	1	4	5	2	1	4	1	10
21	1	1	3	1	1	3	7	1	3	1	1	3	1	7	3	1	1	3	1	1	21	1	1	3	1	1	3	7	1	3
22	1	2	1	2	1	2	1	2	1	2	11	2	1	2	1	2	1	2	1	2	1	22	1	2	1	2	1	2	1	2
23	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	23	1	1	1	1	1	1	1
24	1	2	3	4	1	6	1	8	3	2	1	12	1	2	3	8	1	6	1	4	3	2	1	24	1	2	3	4	1	6
25	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	5	1	1	1	1	25	1	1	1	1	5
26	1	2	1	2	1	2	1	2	1	2	1	2	13	2	1	2	1	2	1	2	1	2	1	2	1	26	1	2	1	2
27	1	1	3	1	1	3	1	1	9	1	1	3	1	1	3	1	1	9	1	1	3	1	1	3	1	1	27	1	1	3
28	1	2	1	4	1	2	7	4	1	2	1	4	1	14	1	4	1	2	1	4	7	2	1	4	1	2	1	28	1	2
29	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	29	1
30	1	2	3	2	5	6	1	2	3	10	1	6	1	2	15	2	1	6	1	10	3	2	1	6	5	2	3	2	1	30

Вариации и обобщения

Понятия простого числа, наибольшего общего делителя и взаимно простых чисел естественно обобщаются на произвольные евклидовы кольца, например, на кольцо многочленов или гауссовы целые числа. Обобщением понятия простого числа является «неприводимый элемент». Данное выше определение взаимно простых чисел не годится для произвольного евклидова кольца, поскольку в кольце могут быть делители единицы; в частности, ${\displaystyle {\text{НОД}}}$ определяется с точностью до умножения на делитель единицы. Поэтому определение взаимно простых чисел следует модифицировать.

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

Равносильные формулировки:

• Элементы евклидова кольца взаимно просты, если они не имеют никаких общих делителей, кроме делителей единицы.
• (Соотношение Безу) Элементы ${\displaystyle a}$, ${\displaystyle b}$ евклидова кольца ${\displaystyle K}$ взаимно просты тогда и только тогда, когда существуют элементы ${\displaystyle u,v\in K}$ такие, что ${\displaystyle au+vb=1}$.

Имеет также место лемма Евклида.

Практическое применение

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

Примечания

1. Взаимно простые числа. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 1. — С. 690.
2. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. — М.: «Мир», 1998. — С. 139. — 703 с. — ISBN 5-03-001793-3.
3. Михелович, 1967, с. 28.
4. Нестеренко Ю. В. Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 40. — 272 с. — ISBN 9785769546464.
5. Михелович, 1967, с. 64.
6. Ларин С. В. Алгебра и теория чисел. Группы, кольца и поля: учеб. пособие для академического бакалавриата. — 2-е изд. — М.: Юрайт, 2018. — С. 92—93. — 160 с. — (Бакалавр. Академический курс). — ISBN 978-5-534-05567-2.

Литература

• Взаимно простые числа // Большая советская энциклопедия : в 66 т. (65 т. и 1 доп.) / гл. ред. О. Ю. Шмидт. — М. : Советская энциклопедия, 1926—1947.
• Михелович Ш. Х. Теория чисел. — 2-е изд. — М.: Высшая школа, 1967. — 336 с.