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

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

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

• НОД( m , n );
• ${\displaystyle (m,n)}$ ;
• ${\displaystyle \gcd(m,n)}$ (от англ. g reatest c ommon d ivisor );
• ${\displaystyle \mathrm {hcf} (m,n)}$ (от брит. h ighest c ommon f actor ).

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

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

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

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

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

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

Это частный случай более общей теоремы: если ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ — ненулевые числа, ${\displaystyle D}$ — какое-либо их общее кратное, то имеет место формула:

${\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)}$

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

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

Аналогично, целые числа ${\displaystyle a_{1},a_{2},\dots a_{k}}$ , где ${\displaystyle k\geq 2}$ , называются взаимно простыми , если их наибольший общий делитель равен единице .

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

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

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

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

${\displaystyle n=p_{1}^{d_{1}}\cdot \dots \cdot p_{k}^{d_{k}},}$

${\displaystyle m=p_{1}^{e_{1}}\cdot \dots \cdot p_{k}^{e_{k}},}$

где ${\displaystyle p_{1},\dots ,p_{k}}$ — различные простые числа, а ${\displaystyle d_{1},\dots ,d_{k}}$ и ${\displaystyle e_{1},\dots ,e_{k}}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД( n , m ) и НОК[ n , m ] выражаются формулами:

${\displaystyle (n,m)=p_{1}^{\min(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\min(d_{k},e_{k})},}$

${\displaystyle [n,m]=p_{1}^{\max(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\max(d_{k},e_{k})}.}$

Если чисел более двух: ${\displaystyle a_{1},a_{2},\dots a_{n}}$ , их НОД находится по следующему алгоритму:

${\displaystyle d_{2}=(a_{1},a_{2})}$

${\displaystyle d_{3}=(d_{2},a_{3})}$

………

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

Свойства

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

${\displaystyle (a_{1}\cdot a_{2},b)=(a_{1},b)\cdot (a_{2},b)}$

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

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

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

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

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

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

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

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

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

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

${\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.}$

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

См. также

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

Литература

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

Примечания