Наибольший общий делитель
Материал из Википедии — свободной энциклопедии
Наибольшим общим делителем (НОД) двух целых чисел m и n называется их общий делитель d (то есть 
и 
), который делится на любой другой общий делитель m и n.
Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Наибольший общий делитель существует и однозначно определён (с точностью до знака), если хотя бы одно из чисел 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](http://upload.wikimedia.org/math/3/7/e/37e2429cfba5c9489e685df64f7131ef.png)
Это частный случай более общей теоремы:
- Если
— ненулевые числа, тогда
![[a_1, a_2, \dots , a_n]=D/(D/a_1, D/a_2, \dots , D/a_n)](http://upload.wikimedia.org/math/4/8/5/485c4926d202a0d8bf596ebb0a558ffa.png)
Числа m и n называются взаимно-простыми, если НОД(m,n) = 1. Аналогично, целые числа 
, где 
, называются взаимно простыми, если их наибольший общий делитель равен единице.
Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.
[править] Свойства
- Пусть известно разложение чисел m и n на простые множители (см. Основная теорема арифметики),
-
- здесь
— различные простые числа, а 
и 
неотрицательные целые числа (они могут быть нулями, если 
в разложении отсутствует). Тогда НОД и НОК выражаются формулами:
![[n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}](http://upload.wikimedia.org/math/8/3/7/83742654bcacc959710156343b16faaf.png)
- Наибольший общий делитель чисел m и n может быть определен как наименьший положительный элемент всех их линейных комбинаций:
-
- и, таким образом (m,n) представим в виде линейной комбинации чисел m и n:
.
- Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы
, порождённая набором 
, — циклическая и порождается одним элементом 
.
[править] Вариации и обобщения
Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца. Примеры: кольцо многочленов или гауссовы целые числа. Определения общего делителя и НОД в произвольном коммутативном кольце аналогичны приведенным выше.
Не во всяком коммутативном кольце НОД существует. Пример:
![R = \mathbb{Z}\left[\sqrt{-3}\right],\quad a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\quad b = \left(1+\sqrt{-3}\right)\cdot 2.](http://upload.wikimedia.org/math/d/5/1/d512ef120313f4121e0579e13255da88.png)
У элементов a, b в кольце R не существует наибольшего общего делителя.
В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы.
[править] См. также
[править] Ссылки
- Расчет НОД онлайн [1].
[править] Литература
- Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
