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

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

Взаимно простые числа — целые числа, не имеющие никаких общих делителей, кроме ±1. Равносильное определение: целые числа взаимно просты, если их наибольший общий делитель (НОД) равен 1.

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

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

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

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

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

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

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

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

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

НОД$(a_{1},a_{2},\dots ,a_{n},b)=$ НОД$(a_{1},b)$ НОД$(a_{2},b)\dots$ НОД$(a_{n},b)$,

где НОД - наибольший общий делитель.

Свойства

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

• Количество натуральных чисел, взаимно простых с натуральным числом $n$, задаётся функцией Эйлера $\varphi (n)$.

• Числа $a$ и $b$ взаимно просты тогда и только тогда, когда существуют целые $x$ и $y$ такие, что $ax+by=1$ (соотношение Безу). Если натуральные числа $a$ и $b$ взаимно просты, то числа $2^{a}-1$ и $2^{b}-1$ также взаимно просты, притом верно и обратное.

• (Лемма Евклида) Если $a$ — делитель произведения $bc$ и $a$ взаимно просто с $b$, то $a$ — делитель $c$.

• Если $d=$ НОД$(a,b)$, то числа ${\frac {a}{d}}$ и ${\frac {b}{d}}$ взаимно просты.

• Дробь является несократимой тогда и только тогда, когда числитель и знаменатель взаимно просты.

• Если числа $a$ и $m$ взаимно просты, то сравнение $ax\equiv b{\pmod {m}}$ для любого $b$ имеет единственное решение по модулю $m.$ В частности, решение сравнения для $b=1$ даёт обратный элемент для $a$ в кольце вычетов по модулю m. (См. Соотношение Безу)

• Вероятность того, что любые $k$ случайным образом выбранных положительных целых чисел будут взаимно просты, равна ${\dfrac {1}{\zeta (k)}}$, в том смысле, что при $N\to \infty$ вероятность того, что $k$ положительных целых чисел, меньших, чем ${\textstyle {N}}$ (и выбранных случайным образом), будут взаимно простыми, стремится к ${\dfrac {1}{\zeta (k)}}$. Здесь $\zeta (k)$ — это дзета-функция Римана.

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

В каждой клетке стоит наибольший общий делитель её координат, и соответствующие взаимно-простым парам координат единицы выделены тёмным. Из описанного выше свойства следует, что средняя плотность тёмных клеток при расширении таблицы до бесконечности станет равна $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

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

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

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

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

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

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

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

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

Литература

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