Взаимная простота

Два целых числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.

Связанные определения

• Если среди чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми (для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают).

Примеры

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

Свойства

• Если числа a₁,…, a_n — попарно взаимно простые числа, то НОК(a₁,…, a_n) = |a₁·…·a_n|.
• Числа a и b взаимно просты тогда и только тогда, когда НОД(a, b) = 1, или, иными словами, существуют целые x и y такие, что ax + by = 1 (см. соотношение Безу).
• Если координатную сетку считать «лесом», в котором из точек с целыми координатами растут «деревья» нулевой толщины, то из начала координат видны только деревья, координаты которых взаимно просты.

См. также

• Простое число
• Наибольший общий делитель
• Наименьшее общее кратное
• Распределённые вычисления

Ссылки

• Как часто встречаются пары взаимно простых чисел?