Наибольший общий делитель
Шаблон:Другие значения/аббревиатура Наибо́льшим о́бщим дели́телем (НОД) для двух целых чисел <math>m</math> и <math>n</math> называется наибольший из их общих делителей<ref>Шаблон:Книга страница 857</ref>. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел <math>m</math> или <math>n</math> не равно нулю.
Возможные обозначения наибольшего общего делителя чисел <math>m</math> и <math>n</math>:
- НОД(m, n);
- <math>( m, n )</math>;
- <math>\gcd( m, n )</math> (от англ. Шаблон:Lang-en2);
- <math>\mathrm{hcf}( m, n )</math> (от брит. highest common factor).
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.
Связанные определения
Наименьшее общее кратное
Шаблон:Main Наименьшее общее кратное (НОК) двух целых чисел <math>m</math> и <math>n</math> — это наименьшее натуральное число, которое делится на <math>m</math> и <math>n</math> (без остатка). Обозначается НОК(m,n) или <math>[m,n]</math>, а в английской литературе <math>\mathrm{lcm}(m,n)</math>.
НОК для ненулевых чисел <math>m</math> и <math>n</math> всегда существует и связан с НОД следующим соотношением:
- <math>(m,n)\cdot[m,n]=m\cdot n</math>
Это частный случай более общей теоремы: если <math>a_1, a_2, \dots , a_n</math> — ненулевые числа, <math>D</math> — какое-либо их общее кратное, то имеет место формула:
- <math>D = [a_1, a_2, \dots , a_n] \cdot \left(\frac{D}{a_1}, \frac{D}{a_2}, \dots , \frac{D}{a_n}\right)</math>
- Причем, НОД от коэффициентов делителей НОК всегда равен 1. Например, НОК<math>(4,6)=12=3*4=2*6</math>. <math>3,2</math> - коэффициенты делителей НОК. НОД<math>(3,2)=1</math>. Представим, что НОД этих коэффициентов >=2. Но ведь тогда число не является НОК своих делителей! И правда, мы просто умножили две части уравнения на C.
- Было:<math>12 = 3*4 = 6*2, 12 =</math>НОД<math>(3,2)</math>
- Стало: <math>C*12 = C*3*4 = C*6*2, C*12 = C*</math>НОД<math>(3,2)</math>
- Вернемся к теореме. Вторая часть - нахождение этого коэффициента. То есть, если <math>D = [a_1,a_2,a_3,...,a_n]</math>, то НОД<math>\left(\frac{D}{a_1},\frac{D}{a_2},\frac{D}{a_3},\dots, \frac{D}{a_n} \right) = 1</math>. Но в другом случае мы узнаем, на какую C умножены обе части уравнения.
Взаимно простые числа
Шаблон:Main Числа <math>m</math> и <math>n</math> называются взаимно простыми, если у них нет общих делителей, кроме <math>\pm 1</math>. Для таких чисел Шаблон:S Обратно, если Шаблон:S то числа взаимно просты.
Аналогично, целые числа <math>a_1, a_2, \dots a_k</math>, где <math>k\geq 2</math>, называются взаимно простыми, если их наибольший общий делитель равен единице.
Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.
Способы вычисления
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.
Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел <math>m</math> и <math>n</math> на простые множители:
- <math>n=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},</math>
- <math>m=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},</math>
где <math>p_1,\dots,p_k</math> — различные простые числа, а <math>d_1,\dots,d_k</math> и <math>e_1,\dots,e_k</math> — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:
- <math>(n,m)=p_1^{\min(d_1,e_1)}\cdot\dots\cdot p_k^{\min(d_k,e_k)},</math>
- <math>[n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.</math>
Если чисел более двух: <math>a_1, a_2,\dots a_n</math>, их НОД находится по следующему алгоритму:
- <math>d_2=(a_1, a_2)</math>
- <math>d_3=(d_2, a_3)</math>
- ………
- <math>d_n=(d_{n-1}, a_n)</math> — это и есть искомый НОД.
Свойства
- Основное свойство: наибольший общий делитель <math>m</math> и <math>n</math> делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
- Следствие 1: множество общих делителей <math>m</math> и <math>n</math> совпадает с множеством делителей НОД(m, n).
- Следствие 2: множество общих кратных <math>m</math> и <math>n</math> совпадает с множеством кратных НОК(m, n).
- Если <math>m</math> делится на <math>n</math>, то НОД(m, n) = n. В частности, НОД(n, n) = n.
- <math>(a, b) = (a - b, b)</math>. В общем случае, если <math>a=b*q+c</math>, где <math>a, b, c, q</math> – целые числа, то <math>(a, b)=(b, c)</math>.
- <math>(a\cdot m, a\cdot n) = |a|\cdot (m, n)</math> — общий множитель можно выносить за знак НОД.
- Если <math>D=(m, n)</math>, то после деления на <math>D</math> числа становятся взаимно простыми, то есть, <math>\left({\frac{m}{D},\frac{n}{D}}\right)=1</math>. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
- Мультипликативность: если <math>a_1, a_2</math> взаимно просты, то:
- <math>(a_1 \cdot a_2, b) = (a_1, b) \cdot (a_2, b)</math>
- Наибольший общий делитель чисел <math>m</math> и <math>n</math> может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:
- <math>\left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\}</math>
- и поэтому <math>(m,n)</math> представим в виде линейной комбинации чисел <math>m</math> и <math>n</math>:
- <math>(m,n) = u\cdot m + v\cdot n</math>.
- Это соотношение называется соотношением Безу, а коэффициенты <math>u</math> и <math>v</math> — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы <math>\mathbb{Z}</math>, порождённая набором <math>\{a_1, a_2, \dots , a_n\}</math>, — циклическая и порождается одним элементом: НОДШаблон:Math.
Вариации и обобщения
Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца, такие, как кольцо многочленов или гауссовы целые числа. Однако, определить <math>\operatorname\text{НОД}\left(a,b\right)</math> как наибольший из общих делителей <math>a</math>, <math>b</math> нельзя, так как в таких кольцах, вообще говоря, не определено отношение порядка. Поэтому в качестве обобщённого определения <math>\operatorname\text{НОД}</math> берётся его основное свойство:
- Наибольшим общим делителем <math>\operatorname\text{НОД}\left(a,b\right)</math> называется тот общий делитель, который делится на все остальные общие делители <math>a</math> и <math>b</math>.
Для натуральных чисел без нуля обобщённое определение эквивалентно прежнему. Для натуральных чисел с нулём <math>\operatorname\text{НОД}\left(0,0\right)</math> по прежнему определению не определён, в то время, как по обобщённому определению <math>\operatorname\text{НОД}\left(0,0\right)=0</math>. Для целых чисел <math>\operatorname\text{НОД}</math> в обобщённом смысле уже не однозначен: противоположное ему число тоже будет <math>\operatorname\text{НОД}</math>. Для гауссовых чисел число различных <math>\operatorname\text{НОД}</math> возрастает до 4.
<math>\operatorname\text{НОД}</math> двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов <math>a</math> и <math>b</math> кольца <math>\mathbb{Z}\left[\sqrt{-3}\right]</math> не существует наибольшего общего делителя:
- <math>a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\qquad b = \left(1+\sqrt{-3}\right)\cdot 2</math>.
В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество <math>\operatorname\text{НОД}</math> равно числу делителей единицы в кольце.
См. также
Литература
- Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.