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

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

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел [math]\displaystyle{ m }[/math] или [math]\displaystyle{ n }[/math] не равно нулю.

Возможные обозначения наибольшего общего делителя чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math]:

НОД(m, n);
[math]\displaystyle{ ( m, n ) }[/math];
[math]\displaystyle{ \gcd( m, n ) }[/math] (от англ. greatest common divisor);
[math]\displaystyle{ \mathrm{hcf}( m, n ) }[/math] (от брит. highest common factor).

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

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

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

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

НОК для ненулевых чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] всегда существует и связан с НОД следующим соотношением:

[math]\displaystyle{ (m,n)\cdot[m,n]=m\cdot n }[/math]

Это частный случай более общей теоремы: если [math]\displaystyle{ a_1, a_2, \dots , a_n }[/math] — ненулевые числа, [math]\displaystyle{ D }[/math] — какое-либо их общее кратное, то имеет место формула:

[math]\displaystyle{ D = [a_1, a_2, \dots , a_n] \cdot \left(\frac{D}{a_1}, \frac{D}{a_2}, \dots , \frac{D}{a_n}\right) }[/math]

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

Числа [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] называются взаимно простыми, если у них нет общих делителей, кроме [math]\displaystyle{ \pm 1 }[/math]. Для таких чисел НОД[math]\displaystyle{ (m,n) = 1 }[/math]. Обратно, если НОД[math]\displaystyle{ (m,n) = 1, }[/math] то числа взаимно просты.

Аналогично, целые числа [math]\displaystyle{ a_1, a_2, \dots a_k }[/math], где [math]\displaystyle{ k\geq 2 }[/math], называются взаимно простыми, если их наибольший общий делитель равен единице.

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

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

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

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] на простые множители:

[math]\displaystyle{ n=p_1^{d_1}\cdot\dots\cdot p_k^{d_k}, }[/math]

[math]\displaystyle{ m=p_1^{e_1}\cdot \dots \cdot p_k^{e_k}, }[/math]

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

[math]\displaystyle{ (n,m)=p_1^{\min(d_1,e_1)}\cdot\dots\cdot p_k^{\min(d_k,e_k)}, }[/math]

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

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

[math]\displaystyle{ d_2=(a_1, a_2) }[/math]

[math]\displaystyle{ d_3=(d_2, a_3) }[/math]

………

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

Свойства

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

[math]\displaystyle{ (a_1 \cdot a_2, b) = (a_1, b) \cdot (a_2, b) }[/math]

Наибольший общий делитель чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

[math]\displaystyle{ \left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\} }[/math]

и поэтому [math]\displaystyle{ (m,n) }[/math] представим в виде линейной комбинации чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math]:

[math]\displaystyle{ (m,n) = u\cdot m + v\cdot n }[/math].

Это соотношение называется соотношением Безу, а коэффициенты [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы [math]\displaystyle{ \mathbb{Z} }[/math], порождённая набором [math]\displaystyle{ \{a_1, a_2, \dots , a_n\} }[/math], — циклическая и порождается одним элементом: НОД(a₁, a₂, … , a_n).

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

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

Наибольшим общим делителем НОД(a, b) называется тот общий делитель, который делится на все остальные общие делители [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math].

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

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

[math]\displaystyle{ a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\qquad b = \left(1+\sqrt{-3}\right)\cdot 2. }[/math]

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

См. также

Литература

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

Примечания

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

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

[1]