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

Материал из Википедии — свободной энциклопедии

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

Числа m и n называются взаимно-простыми, если (m,n)=1.

Эффективным способом вычисления наибольшего общего делителя является алгоритм Евклида.

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

Поскольку понятие делимости целых чисел естественно обобщается на рациональные числа (например, 0.5 делится нацело на 0.25, а 0.25 на 0.5 нацело не делится), то понятия НОД и НОК распространяются и на наборы рациональных чисел.

[править] Связанные определения

Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее целое число которое делится на m и n. Обычно обозначается $[n, m]$ , а иногда НОК(m,n) или LCM(m,n).
Набор целых чисел $a_1, a_2, \dots a_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_k\!$ и $e_k\!$ неотрицательные целые числа (они могут быть нулями, если $p_k\!$ в разложении отсутствует). Тогда НОД и НОК выражаются формулами:

$(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)}$

Для любых m и n

$(n,m)\cdot[n,m]=n\cdot m$ - это частный случай более общей теоремы:

Если $D, a_1, a_2, \dots , a_n$ — ненулевые рациональные числа, тогда

$[a_1, a_2, \dots , a_n]=D/(D/a_1, D/a_2, \dots , D/a_n)$

Наибольший общий делитель чисел 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)$ .

Категория: Теория чисел

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

Материал из Википедии — свободной энциклопедии

[править] Связанные определения

[править] Свойства

Views

Навигация

Участие

Поиск

На других языках