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

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

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

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

Обозначения


 Для указания взаимной простоты чисел mm и n используется обозначение:

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

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



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

Примеры



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

Свойства



  • Числа a и b взаимно просты тогда и только тогда, когда выполняется одно из эквивалентных условий:
    • наибольший общий делитель a и b равен единице;
    • существуют целые x и y такие, что ax+by=1 (соотношение Безу).

  • Любые два (различных) простых числа взаимно просты.
  • Если a — делитель произведения bc, и a взаимно просто с b, то a — делитель c.
  • Если числа a1,,an — попарно взаимно простые числа, то НОК(a1,,an)=|a1an|. Например, НОК (9,11)=911=99.
  • Вероятность того, что любые k случайным образом выбранных положительных целых чисел будут взаимно просты, равна 1ζ(k), в том смысле, что при N вероятность того, что k положительных целых чисел, меньших, чем N (и выбранных случайным образом) будут взаимно простыми, стремится к 1ζ(k). Здесь ζ(k) — это дзета-функция Римана.
  • Дробь является несократимой тогда и только тогда, когда числитель и знаменатель взаимно просты.

Обобщения


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

Применение


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