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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

  • НОД(m,n)
  • (m,n)
  • \gcd(m,n) (от англ. Greatest Common Divisor)
  • \mathrm{hcf}(m,n) (от брит. англ. Highest Common Factor)

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

Связанные определения[править | править вики-текст]

Наименьшее общее кратное[править | править вики-текст]

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n], а в английской литературе \mathrm{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\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\}, — циклическая и порождается одним элементом: НОД(a1, a2, … , an).

Вариации и обобщения[править | править вики-текст]

Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца, такие, как кольцо многочленов или гауссовы целые числа. Однако, определить НОД(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.

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Примечания[править | править вики-текст]