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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Числа 4 и 9 взаимно простые, следовательно, диагональ решетки 4 на 9 не пересекает других точек решетки

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

Примеры:

  • 14 и 25 взаимно просты — у них нет общих делителей.
  • 15 и 25 не взаимно просты (у них имеется общий делитель 5).
  • 6, 8, 9 взаимно просты — у них нет делителей, общих для всех трёх чисел.

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

Обозначения[править | править исходный текст]

Для указания взаимной простоты чисел ~m и n \, используется обозначение[1]:

m \perp n.
« Подобно тому, как перпендикулярные прямые не имеют общего направления, так и перпендикулярные числа не имеют общих сомножителей.[1] »

Однако не все математики признают и используют это обозначение. Чаще всего используется словесная формулировка или эквивалентная запись (a, b)=1, что означает: «наибольший общий делитель чисел a и b равен 1».

Связанные определения[править | править исходный текст]

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

Примеры[править | править исходный текст]

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

Свойства[править | править исходный текст]

  • Числа a и b взаимно просты тогда и только тогда, когда выполняется одно из эквивалентных условий.
  • Любые два (различных) простых числа взаимно просты.
  • Если a — делитель произведения bc, и a взаимно просто с b, то a — делитель c.
  • Если числа a1,…, an — попарно взаимно простые числа, то НОК(a1, …, an) = |a1·…·an|. Например, НОК(9, 11) = 9 \cdot 11 = 99.
  • Вероятность того, что любые три случайным образом выбранных положительных целых числа будут взаимно просты, равна 1/ζ(3), в том смысле, что при N\to\infty вероятность того, что три положительных целых числа, меньших, чем {\textstyle{N}} (и выбранных случайным образом) будут взаимно простыми, стремится к 1/ζ(3) (постоянная Апери).

Обобщения[править | править исходный текст]

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

Применение[править | править исходный текст]

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. 1 2 Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. — М.: «Мир», 1998. — С. 139. — 703 с. — ISBN 5-03-001793-3

Ссылки[править | править исходный текст]