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

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

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

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

• НОД(m, n)
• (m, n)
• gcd(m, n) (от англ. Greatest Common Divisor)

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

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

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

Основная статья: Наименьшее общее кратное

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или $[m,n]$, а в английской литературе lcm(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 \left({\frac {D}{a_{1}}},{\frac {D}{a_{2}}},\dots ,{\frac {D}{a_{n}}}\right)$

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

Основная статья: Взаимно простые числа

Числа m и n называются взаимно-простыми, если у них нет общих делителей, кроме единицы. Для таких чисел НОД(m,n) = 1. Обратно, если НОД(m,n) = 1, то числа взаимно просты.

Аналогично, целые числа $a_{1},a_{2},\dots a_{k}$, где $k\geq 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}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(m,n) и НОК(m,n) выражаются формулами:

$(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\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 может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

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