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

---

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

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

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

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

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

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

---