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

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

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

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

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

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

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

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

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

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

( m , n ) ⋅ [ m , n ] = m ⋅ n {displaystyle (m,n)cdot [m,n]=mcdot n}

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

D = [ a 1 , a 2 , … , a n ] ⋅ ( D a 1 , D a 2 , … , D a n ) {displaystyle D=[a_{1},a_{2},dots ,a_{n}]cdot left({frac {D}{a_{1}}},{frac {D}{a_{2}}},dots ,{frac {D}{a_{n}}} ight)}

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

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

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

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

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

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

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

n = p 1 d 1 ⋅ ⋯ ⋅ p k d k , {displaystyle n=p_{1}^{d_{1}}cdot dots cdot p_{k}^{d_{k}},} m = p 1 e 1 ⋅ ⋯ ⋅ p k e k , {displaystyle m=p_{1}^{e_{1}}cdot dots cdot p_{k}^{e_{k}},}

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

( n , m ) = p 1 min ( d 1 , e 1 ) ⋅ ⋯ ⋅ p k min ( d k , e k ) , {displaystyle (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 ) ⋅ ⋯ ⋅ p k max ( d k , e k ) . {displaystyle [n,m]=p_{1}^{max(d_{1},e_{1})}cdot dots cdot p_{k}^{max(d_{k},e_{k})}.}

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

d 2 = ( a 1 , a 2 ) {displaystyle d_{2}=(a_{1},a_{2})} d 3 = ( d 2 , a 3 ) {displaystyle d_{3}=(d_{2},a_{3})} ……… d n = ( d n − 1 , a n ) {displaystyle d_{n}=(d_{n-1},a_{n})} — это и есть искомый НОД.

Свойства

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

( a 1 ⋅ a 2 , b ) = ( a 1 , b ) ⋅ ( a 2 , b ) {displaystyle (a_{1}cdot a_{2},b)=(a_{1},b)cdot (a_{2},b)}

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

{ a ⋅ m + b ⋅ n ∣ a , b ∈ Z } {displaystyle left{acdot m+bcdot nmid a,bin mathbb {Z} ight}} и поэтому ( m , n ) {displaystyle (m,n)} представим в виде линейной комбинации чисел m {displaystyle m} и n {displaystyle n} : ( m , n ) = u ⋅ m + v ⋅ n {displaystyle (m,n)=ucdot m+vcdot n} . Это соотношение называется соотношением Безу, а коэффициенты u {displaystyle u} и v {displaystyle v} — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы Z {displaystyle mathbb {Z} } , порождённая набором { a 1 , a 2 , … , a n } {displaystyle {a_{1},a_{2},dots ,a_{n}}} , — циклическая и порождается одним элементом: НОД(a1, a2, … , an).

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

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

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

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

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

a = 4 = 2 ⋅ 2 = ( 1 + − 3 ) ( 1 − − 3 ) , b = ( 1 + − 3 ) ⋅ 2. {displaystyle a=4=2cdot 2=left(1+{sqrt {-3}} ight)left(1-{sqrt {-3}} ight),qquad b=left(1+{sqrt {-3}} ight)cdot 2.}

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