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

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

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

Возможные обозначения наибольшего общего делителя чисел и :

  • НОД(m, n);
  • ;
  • (от англ. greatest common divisor);
  • (от брит. highest common factor).

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

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

править

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

править

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

НОК для ненулевых чисел   и   всегда существует и связан с НОД следующим соотношением:

 

Это частный случай более общей теоремы: если   — ненулевые числа,   — какое-либо их общее кратное, то имеет место формула:

 
Причем, НОД от коэффициентов делителей НОК всегда равен 1. Например, НОК .   - коэффициенты делителей НОК. НОД . Представим, что НОД этих коэффициентов >=2. Но ведь тогда число не является НОК своих делителей! И правда, мы просто умножили две части уравнения на C.
Было: НОД 
Стало:  НОД 
Вернемся к теореме. Вторая часть - нахождение этого коэффициента. То есть, если  , то НОД . Но в другом случае мы узнаем, на какую C умножены обе части уравнения.

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

править

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

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

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 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.
  •  . В общем случае, если  , где   – целые числа, то  .
  •   — общий множитель можно выносить за знак НОД.
  • Если  , то после деления на   числа становятся взаимно простыми, то есть,  . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
  • Мультипликативность: если   взаимно просты, то:
 
  • Наибольший общий делитель чисел   и   может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:
 
и поэтому   представим в виде линейной комбинации чисел   и  :
 .
Это соотношение называется соотношением Безу, а коэффициенты   и   — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы  , порождённая набором  , — циклическая и порождается одним элементом: НОД(a1, a2, … , an).

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

править

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

Наибольшим общим делителем НОД(a, b) называется тот общий делитель, который делится на все остальные общие делители   и  .

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

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

 

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

См. также

править

Литература

править

Примечания

править
  1. Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. Архивировано 16 октября 2013 года. страница 857