WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

Кроме того, значение НОД(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\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 с.

Примечания