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

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

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.[1] Пример: для чисел 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\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.

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

См. также

Литература

Примечания


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Наибольший общий делитель" в других словарях:

  • НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ — наибольшее из целых положительных чисел, на которое делится без остатка каждое из данных целых чисел. Напр., наибольший общий делитель 60, 84 и 96 есть 12 …   Большой Энциклопедический словарь

  • наибольший общий делитель — НОД — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации Синонимы НОД EN greatest common divisorgcd …   Справочник технического переводчика

  • наибольший общий делитель — наибольшее из целых положительных чисел, на которое делится без остатка каждое из данных целых чисел. Например, наибольший общий делитель 60, 84 и 96 есть 12. * * * НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ, наибольшее из целых… …   Энциклопедический словарь

  • НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ — наибольший из общих делителей целых, в частности натуральных, чисел . Если данные числа не все равны нулю, то такой делитель существует. Н. о. д. чисел обычно обозначают символом Свойства Н. о. д.: 1) Н. о. д. чисел делится на любой общий… …   Математическая энциклопедия

  • Наибольший общий делитель —         двух или нескольких натуральных чисел наибольшее из чисел, на которые делится каждое из данных чисел. Например, Н. о. д. 45 и 72 есть 9, Н. о. д. 60, 84, 96 и 120 есть 12. Н. о. д. пользуются при сокращении дробей: наибольшее число, на… …   Большая советская энциклопедия

  • НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ — наибольшее из целых положит. чисел, на к рое делится без остатка каждое из данных целых чисел. Напр., И.о. д. 60, 84 и 96 есть 12 …   Естествознание. Энциклопедический словарь

  • Делитель (значения) — Делитель (математика) Наибольший общий делитель Делитель нуля в абстрактной алгебре Делитель единицы Делитель напряжения Делитель тока Делитель мощности Делитель комбинационное логическое устройство в электронике Делитель потока дроссельный или… …   Википедия

  • ДЕЛИТЕЛЬ — ДЕЛИТЕЛЬ, я, муж. Число или величина, на к рую делится делимое. Наибольший общий д. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 …   Толковый словарь Ожегова

  • наибольший — ▲ самый ↑ большой наибольший самый большой (# общий делитель). наивысший. высший. максимальный …   Идеографический словарь русского языка

  • ОБЩИЙ — общая, общее (кратк. формы общ, обща, обще книжн., мало употр.). 1. Коллективный, совместный с другими, принадлежащий всем. «…Национальная общность немыслима без общего языка…» Сталин. Общее мнение. Общее решение. Общее дело. Общая кухня. Общая… …   Толковый словарь Ушакова


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»