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

2026-01-28T22:40:17Z

94.142.17.130: /* Вариации и обобщения */ замена «новое определение» → «обобщённое определение», стиль формул → math

{{Другие значения/аббревиатура|НОД|Нод|Нод}}
'''Наибо́льшим о́бщим дели́телем''' ('''НОД''') для двух [[целое число|целых чисел]] <math>m</math> и <math>n</math> называется наибольший из их [[Общий делитель|общих делителей]]<ref>{{книга |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |год=1982 |том=3 |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t3.djvu |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] |archive-date=2013-10-16 |archive-url=https://web.archive.org/web/20131016140955/http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t3.djvu }} страница 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-en|'''g'''reatest '''c'''ommon '''d'''ivisor}});
* <math>\mathrm{hcf}( m, n )</math> (от [[Британский вариант английского языка|брит.]] '''''h'''ighest '''c'''ommon '''f'''actor'').

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

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

=== Наименьшее общее кратное ===
{{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|НОД<math>(m,n) = 1</math>.}} Обратно, если {{s|НОД<math>(m,n) = 1,</math>}} то числа взаимно просты.

Аналогично, [[целое число|целые числа]] <math>a_1, a_2, \dots a_k</math>, где <math>k\geq 2</math>, называются '''взаимно простыми''', если их наибольший общий делитель равен [[1 (число)|единице]].

Следует различать понятия ''взаимной простоты'', когда НОД набора чисел равен 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>
:: <big>………</big>
: <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|(''a''1, ''a''2, … , ''a''''n'')}}.

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

Понятие делимости целых чисел естественно обобщается на произвольные [[коммутативное кольцо|коммутативные кольца]], такие, как [[кольцо многочленов]] или [[гауссовы целые числа]]. Однако, определить <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> равно числу делителей единицы в кольце.

== См. также ==
* [[Бинарный алгоритм вычисления НОД]]
* [[Делимость]]
* [[Алгоритм Евклида]]
* [[Наименьшее общее кратное]]

== Литература ==
* ''Виноградов И. М.'' [http://math.ru/lib/book/djvu/vinogradov.djvu Основы теории чисел.] М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

== Примечания ==
{{примечания}}

[[Категория:Теория чисел]]
[[Категория:Делимость и остатки]]

wiki12 - Вклад [ru]

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