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

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

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

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

• НОД(m, n);
• $(m,n)$;
• $\gcd (m,n)$ (от Шаблон:Lang-en);
• $\mathrm{h}\mathrm{c}\mathrm{f}(m,n)$ (от брит. highest common factor).

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

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

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

Шаблон:Main Наименьшее общее кратное (НОК) двух целых чисел $m$ и $n$ — это наименьшее натуральное число, которое делится на $m$ и $n$ (без остатка). Обозначается НОК(m,n) или $[m,n]$, а в английской литературе $\mathrm{l}\mathrm{c}\mathrm{m}(m,n)$.

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

$(m,n)\cdot [m,n]=m\cdot n$

Это частный случай более общей теоремы: если $a_1,a_2,\dots ,a_n$ — ненулевые числа, $D$ — какое-либо их общее кратное, то имеет место формула:

$D=[a_1,a_2,\dots ,a_n]\cdot (\frac{D}{a_1},\frac{D}{a_2},\dots ,\frac{D}{a_n})$

Причем, НОД от коэффициентов делителей НОК всегда равен 1. Например, НОК$(4,6)=12=3*4=2*6$. $3,2$ - коэффициенты делителей НОК. НОД$(3,2)=1$. Представим, что НОД этих коэффициентов >=2. Но ведь тогда число не является НОК своих делителей! И правда, мы просто умножили две части уравнения на C.

Было:$12=3*4=6*2,12=$НОД$(3,2)$

Стало: $C*12=C*3*4=C*6*2,C*12=C*$НОД$(3,2)$

Вернемся к теореме. Вторая часть - нахождение этого коэффициента. То есть, если $D=[a_1,a_2,a_3,...,a_n]$, то НОД$(\frac{D}{a_1},\frac{D}{a_2},\frac{D}{a_3},\dots ,\frac{D}{a_n})=1$. Но в другом случае мы узнаем, на какую C умножены обе части уравнения.

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

Шаблон:Main Числа $m$ и $n$ называются взаимно простыми, если у них нет общих делителей, кроме $\pm 1$. Для таких чисел Шаблон:S Обратно, если Шаблон:S то числа взаимно просты.

Аналогично, целые числа $a_1,a_2,\dots a_k$, где $k\ge 2$, называются взаимно простыми, если их наибольший общий делитель равен единице.

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

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

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

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел $m$ и $n$ на простые множители:

$n=p_1^{d_1}\cdot \dots \cdot p_k^{d_k},$

$m=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},$

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

$(n,m)=p_1^{\min (d_1,e_1)}\cdot \dots \cdot p_k^{\min (d_k,e_k)},$

$[n,m]=p_1^{\max (d_1,e_1)}\cdot \dots \cdot p_k^{\max (d_k,e_k)}.$

Если чисел более двух: $a_1,a_2,\dots a_n$, их НОД находится по следующему алгоритму:

$d_2=(a_1,a_2)$

$d_3=(d_2,a_3)$

………

$d_n=(d_{n-1},a_n)$ — это и есть искомый НОД.

Свойства

• Основное свойство: наибольший общий делитель $m$ и $n$ делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
  • Следствие 1: множество общих делителей $m$ и $n$ совпадает с множеством делителей НОД(m, n).
  • Следствие 2: множество общих кратных $m$ и $n$ совпадает с множеством кратных НОК(m, n).
• Если $m$ делится на $n$, то НОД(m, n) = n. В частности, НОД(n, n) = n.
• $(a,b)=(a-b,b)$. В общем случае, если $a=b*q+c$, где $a,b,c,q$ – целые числа, то $(a,b)=(b,c)$.
• $(a\cdot m,a\cdot n)=|a|\cdot (m,n)$ — общий множитель можно выносить за знак НОД.
• Если $D=(m,n)$, то после деления на $D$ числа становятся взаимно простыми, то есть, $\left(\frac{m}{D},\frac{n}{D}\right)=1$. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
• Мультипликативность: если $a_1,a_2$ взаимно просты, то:

$(a_1\cdot a_2,b)=(a_1,b)\cdot (a_2,b)$

• Наибольший общий делитель чисел $m$ и $n$ может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

$\{a\cdot m+b\cdot n\mid a,b\in \mathbb{Z}\}$

и поэтому $(m,n)$ представим в виде линейной комбинации чисел $m$ и $n$:

$(m,n)=u\cdot m+v\cdot n$.

Это соотношение называется соотношением Безу, а коэффициенты $u$ и $v$ — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы $\mathbb{Z}$, порождённая набором $\{a_1,a_2,\dots ,a_n\}$, — циклическая и порождается одним элементом: НОДШаблон:Math.

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

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

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

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

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов $a$ и $b$ кольца $\mathbb{Z}\left[\sqrt{-3}\right]$ не существует наибольшего общего делителя:

$a=4=2\cdot 2=(1+\sqrt{-3})(1-\sqrt{-3}),b=(1+\sqrt{-3})\cdot 2.$

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

См. также

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

Литература

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