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

Материал из Википедии — свободной энциклопедии

Два целых числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Примеры: 14 и 25 взаимно просты, а 15 и 25 не взаимно просты (у них имеется общий делитель 5).

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

[править] Обозначения

Для взаимно простых чисел существует специальное обозначение ^[1]. Если целых числа и n взаимно просты, то это записывают так:

Подобно тому, как перпендикулярные прямые не имеют общего направления, так и перпендикулярные числа не имеют общих сомножителей.

— Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. — С. 139.

[править] Связанные определения

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

[править] Примеры

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

[править] Свойства

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

[править] Обобщения

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

[править] Примечания

[править] См. также

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

[править] Ссылки

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