Processing math: 100%

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

Наибольшим общим делителем (НОД) для двух целых чиселm и n называется наибольший из их общих делителей. Пример: для чисел54 и 24 наибольший общий делитель равен 6.
 Наибольший общий делитель существует и однозначно определён, если хотябы одно из чисел m или n не равно нулю.
 Возможные обозначения наибольшего общего делителя чисел m и n:

  • НОД(m, n);
  • (m,n);
  • gcd(m,n) (от );
  • hcf(m,n) (от брит. highest common factor).

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

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


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


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

(m,n)[m,n]=mn
 Это частный случай более общей теоремы: если a1,a2,,an —ненулевые числа, D — какое-либо их общее кратное, то имеет местоформула:

D=[a1,a2,,an](Da1,Da2,,Dan)

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


 Числа m и n называются взаимно простыми, если у них нетобщих делителей, кроме единицы. Для таких чисел НОД(m,n) =1. Обратно, если НОД(m,n) = 1, то числа взаимно просты.
 Аналогично, целые числа a1,a2,ak, где k2, называютсявзаимно простыми, если их наибольший общий делитель равенединице.
 Следует различать понятия взаимной простоты, когда НОД наборачисел равен 1, и попарной взаимной простоты, когда НОД равен 1для каждой пары чисел из набора. Из попарной простоты вытекает взаимнаяпростота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары изэтого набора не взаимно просты.

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


 Эффективными способами вычисления НОД двух чисел являются алгоритмЕвклида и бинарный алгоритм.
 Кроме того, значение НОД(m,n) можно легко вычислить, еслиизвестно каноническое разложение чисел m и n на простые множители:


n=pd11pdkk,
m=pe11pekk,

 где p1,,pk — различные простые числа, а d1,,dk иe1,,ek — неотрицательные целые числа (они могут быть нулями,если соответствующее простое отсутствует в разложении). ТогдаНОД(m,n) и НОК(m,n) выражаются формулами:


(n,m)=pmin(d1,e1)1pmin(dk,ek)k,
[n,m]=pmax(d1,e1)1pmax(dk,ek)k.

 Если чисел более двух: a1,a2,an, их НОД находится последующему алгоритму:

d2=(a1,a2)
d3=(d2,a3)

 \ldots\ldots\ldots
dn=(dn1,an) — это и есть искомый НОД.

Свойства



  • Основное свойство: наибольший общий делитель 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.
  • (am,an)=|a|(m,n) — общий множитель можно выносить за знак НОД.
  • Если D=(m,n), то после деления на D числа становятся взаимно простыми, то есть, (mD,nD)=1. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
  • Мультипликативность: если a1,a2 взаимно просты, то:


(a1a2,b)=(a1,b)(a2,b)

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



{am+bna,b\Z}

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


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


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

 Для натуральных чисел новое определение эквивалентно старому. Для целыхчисел НОД в новом смысле уже не однозначен: противоположное ему числотоже будет НОД. Для гауссовых чисел число различных НОД возрастает до 4.
 НОД двух элементов коммутативного кольца, вообще говоря, не обязансуществовать. Например, для нижеследующих элементов a и b кольцаZ[3] не существует наибольшего общегоделителя:

a=4=22=(1+3)(13),b=(1+3)2.
 В евклидовых кольцах наибольший общий делитель всегда существует иопределён с точностью до делителей единицы, то есть количество НОД равночислу делителей единицы в кольце.