Наибольший общий делитель

Наибольшим общим делителем (НОД) для двух целых чисел  и  называется наибольший из их общих делителей. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел  или  не равно нулю.

Возможные обозначения наибольшего общего делителя чисел  и :
 НОД(m, n);
 ;
  (от );
  (от брит. highest common factor).

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

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

Наименьшее общее кратное 

Наименьшее общее кратное (НОК) двух целых чисел  и  — это наименьшее натуральное число, которое делится на  и  (без остатка). Обозначается НОК(m,n) или , а в английской литературе .

НОК для ненулевых чисел  и  всегда существует и связан с НОД следующим соотношением:
 
Это частный случай более общей теоремы: если  — ненулевые числа,  — какое-либо их общее кратное, то имеет место формула:

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

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

Аналогично, целые числа , где , называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

Способы вычисления 

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел  и  на простые множители:
 
 
где  — различные простые числа, а  и  — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:
 
 

Если чисел более двух: , их НОД находится по следующему алгоритму:
 
 
 ………
  — это и есть искомый НОД.

Свойства 
 Основное свойство: наибольший общий делитель  и  делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
 Следствие 1: множество общих делителей  и  совпадает с множеством делителей НОД(m, n).
 Следствие 2: множество общих кратных  и  совпадает с множеством кратных НОК(m, n).
 Если  делится на , то НОД(m, n) = n. В частности, НОД(n, n) = n.
. В общем случае, если , где  – целые числа, то .
  — общий множитель можно выносить за знак НОД.
 Если , то после деления на  числа становятся взаимно простыми, то есть, . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
 Мультипликативность: если  взаимно просты, то:
 
 Наибольший общий делитель чисел  и  может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:
 
 и поэтому  представим в виде линейной комбинации чисел  и :
 .
 Это соотношение называется соотношением Безу, а коэффициенты  и  — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД.

Вариации и обобщения 

Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца, такие, как кольцо многочленов или гауссовы целые числа. Однако, определить  как наибольший из общих делителей ,  нельзя, так как в таких кольцах, вообще говоря, не определено отношение порядка. Поэтому в качестве определения НОД берётся его основное свойство:
 Наибольшим общим делителем НОД(a, b) называется тот общий делитель, который делится на все остальные общие делители  и .
Для натуральных чисел новое определение эквивалентно старому. Для целых чисел НОД в новом смысле уже не однозначен: противоположное ему число тоже будет НОД. Для гауссовых чисел число различных НОД возрастает до 4.

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов  и  кольца  не существует наибольшего общего делителя:
 

В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество НОД равно числу делителей единицы в кольце.

См. также 
 Бинарный алгоритм вычисления НОД
 Делимость
 Алгоритм Евклида
 Наименьшее общее кратное

Литература 
 Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Примечания 

Теория чисел
Делимость и остатки