Например, взаимно просты числа и , так как у них нет общих делителей; но числа и не взаимно просты, так как у них имеется общий делитель .
Для указания взаимной простоты чисел и иногда используется обозначение (аналогия с перпендикулярными прямыми, не имеющими общих направлений — взаимно простые числа не имеют общих сомножителей[2]).
Это понятие было введено в книге VII «Начал»Евклида. Для определения того, являются ли два числа взаимно простыми, можно использовать алгоритм Евклида.
Понятие взаимной простоты естественным образом обобщается на любые евклидовы кольца[⇨].
Если в наборе целых чисел любые два числа взаимно просты, то такие числа называются попарно взаимно простыми (или просто попарно простыми[3]). Для двух чисел понятия «взаимно простые» и «попарно простые» совпадают, для более чем двух чисел свойство попарной простоты более сильно, чем ранее определённое свойство взаимной простоты (в совокупности) — попарно простые числа будут и взаимно простыми, но обратное неверно[3]. Примеры:
— не простые, но взаимно простые.
— взаимно простые (в совокупности) числа, но не попарно простые.
— попарно простые и взаимно простые (в совокупности).
Вероятность того, что случайным образом выбранных положительных целых числа будут взаимно просты, равна , в том смысле, что при вероятность того, что положительных целых чисел, меньших, чем (и выбранных случайным образом), будут взаимно простыми, стремится к . Здесь — это дзета-функция Римана.
Таблица взаимной простоты чисел до 30
В каждой клетке стоит наибольший общий делитель её координат, и соответствующие взаимно-простым парам координат единицы выделены тёмным. Из описанного выше свойства следует, что средняя плотность тёмных клеток при расширении таблицы до бесконечности станет равна .
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
Вариации и обобщения
Понятия простого числа, наибольшего общего делителя и взаимно простых чисел естественно обобщаются на произвольные евклидовы кольца, например, на кольцо многочленов или гауссовы целые числа. Обобщением понятия простого числа является «неприводимый элемент». Данное выше определение взаимно простых чисел не годится для произвольного евклидова кольца, поскольку в кольце могут быть делители единицы; в частности, определяется с точностью до умножения на делитель единицы. Поэтому определение взаимно простых чисел следует модифицировать[6].
Элементы евклидова кольца называются взаимно простыми, если множество их наибольших общих делителей содержит только делители единицы.
Свойство взаимной простоты не только играет важную роль в теории чисел и коммутативной алгебре, но имеет ряд важных практических приложений, в частности, число зубьев на звёздочках и число звеньев цепи в цепной передаче стремятся делать взаимно простыми, что обеспечивает равномерность износа: каждый зуб звёздочки будет поочерёдно работать со всеми звеньями цепи.
Примечания
↑ 12Взаимно простые числа. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 1. — С. 690.
↑ 12Ларин С. В. Алгебра и теория чисел. Группы, кольца и поля: учеб. пособие для академического бакалавриата. — 2-е изд. — М.: Юрайт, 2018. — С. 92—93. — 160 с. — (Бакалавр. Академический курс). — ISBN 978-5-534-05567-2.