Взаимно простые числа — целые числа , не имеющие никаких общих делителей , кроме ${\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}$ .

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

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

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

Примечания

Литература

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