Наибо́льшим о́бщим дели́телем (НОД) для двух целых чисел и называется наибольший из их общих делителей страница 857. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел или не равно нулю.
Возможные обозначения наибольшего общего делителя чисел и : НОД(m, n); ; (от ); (от брит. highest common factor).
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.
Связанные определения
Наименьшее общее кратное
Наименьшее общее кратное (НОК) двух целых чисел и — это наименьшее натуральное число, которое делится на и (без остатка). Обозначается НОК(m,n) или , а в английской литературе .
НОК для ненулевых чисел и всегда существует и связан с НОД следующим соотношением:
Это частный случай более общей теоремы: если — ненулевые числа, — какое-либо их общее кратное, то имеет место формула:
Взаимно простые числа
Числа и называются взаимно простыми, если у них нет общих делителей, кроме . Для таких чисел Обратно, если то числа взаимно просты.
Аналогично, целые числа , где , называются взаимно простыми, если их наибольший общий делитель равен единице.
Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.
Способы вычисления
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.
Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел и на простые множители:
где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:
Если чисел более двух: , их НОД находится по следующему алгоритму:
……… — это и есть искомый НОД.
Свойства Основное свойство: наибольший общий делитель и делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6. Следствие 1: множество общих делителей и совпадает с множеством делителей НОД(m, n). Следствие 2: множество общих кратных и совпадает с множеством кратных НОК(m, n). Если делится на , то НОД(m, n) = n. В частности, НОД(n, n) = n. . В общем случае, если , где – целые числа, то . — общий множитель можно выносить за знак НОД. Если , то после деления на числа становятся взаимно простыми, то есть, . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД. Мультипликативность: если взаимно просты, то:
Наибольший общий делитель чисел и может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:
и поэтому представим в виде линейной комбинации чисел и : . Это соотношение называется соотношением Безу, а коэффициенты и — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД.
Вариации и обобщения
Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца, такие, как кольцо многочленов или гауссовы целые числа. Однако, определить как наибольший из общих делителей , нельзя, так как в таких кольцах, вообще говоря, не определено отношение порядка. Поэтому в качестве обобщённого определения берётся его основное свойство: Наибольшим общим делителем называется тот общий делитель, который делится на все остальные общие делители и . Для натуральных чисел без нуля обобщённое определение эквивалентно прежнему. Для натуральных чисел с нулём по прежнему определению не определён, в то время, как по обобщённому определению . Для целых чисел в обобщённом смысле уже не однозначен: противоположное ему число тоже будет . Для гауссовых чисел число различных возрастает до 4.
двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов и кольца не существует наибольшего общего делителя: .
В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество равно числу делителей единицы в кольце.
См. также Бинарный алгоритм вычисления НОД Делимость Алгоритм Евклида Наименьшее общее кратное
Литература Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Примечания
Категория:Теория чисел Категория:Делимость и остатки