Изменения

{{В разработкеОпределение|definition='''Наибольшим общим делителем''' (англ. <tex>\gcd</tex> {{---}} ''greatest common divisor'') для двух целых чисел <tex>a</tex> и <tex>b</tex> называется наибольшее натуральное <tex>d</tex>, такое что <tex>a</tex> делится на <tex>d</tex> и <tex>b</tex> делится на <tex>d</tex>. Более формально, <tex>\gcd(a, b) =\max \left\{ d \mid a \equiv 0 \left(\bmod d\right), b \equiv 0 \left(\bmod d\right) \right\}</tex>}} ==Свойства НОД== Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел <tex>m</tex> или <tex>n</tex> не ноль. Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел: {{Определение|definition='''Наибольший общий делитель''' для целочисленного множества <tex>A</tex> определяется как <tex>\gcd(A) = \max \left\{ d \mid \forall a_j \in A,\: a_j \equiv 0 \left(\bmod d \right)\right\}</tex>}}

Существует определение НОД через [[Разложение_на_множители_(факторизация) | разложение числа на простые множители]]: {{Утверждение|id=l001|statement=Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа. Тогда <tex dpi="140">\gcd(a, b) =Наибольший общий p_1^{\min(\alpha_1, \beta_1)}\cdot p_2^{\min(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\min(\alpha_k, \beta_k)},</tex> где <tex>p_j</tex> — делитель как максимальное число<tex>a</tex> и <tex>b</tex>. (Если <tex>a</tex> не делится на <tex>p_j,</tex> будем считать, что <tex>p_j</tex> присутствует в разложении <tex>a</tex> в <tex>0</tex>-ой степени.)|proof=Разложим <tex>a</tex> и <tex>b</tex> на множители: пусть <tex dpi="140">a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dotso \cdot p_k^{\alpha_k}, \: b = q_1^{\beta_1} \cdot q_2^{\beta_2} \cdot \dotso \cdot q_k^{\beta_k}</tex>, где <tex>p_j, q_j</tex> {{---}} простые, а <tex>\alpha_j, \beta_j</tex> {{---}} натуральные(такие разложения существуют, по [[Основная_теорема_арифметики | основной теореме арифметики]]). Без ограничения общности, можно считать, что <tex>p_j = q_j, k = n</tex> (если это не так, сделаем соответствующие <tex>\alpha</tex> и <tex>\beta</tex> равными нулю).Очевидно, что в таком случае <tex>a</tex> и на <tex>b</tex> делятся на <tex dpi="140">p = p_1^{\min(\alpha_1, \beta_1)}\cdot p_2^{\min(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\min(\alpha_k, \beta_k)} </tex>. Проверим его максимальность.Пусть существует <tex>q > p</tex>, такое что <tex>a</tex> и <tex>b</tex> делятся на <tex>q</tex>. Тогда оно необходимо будет раскладываться на те же простые множители, что и <tex>p</tex>.Пусть <tex dpi="140">q = p_1^{\gamma_1}\cdot p_2^{\gamma_2} \cdot \dotso \cdot p_k^{\gamma_k} </tex>. Значит, существует <tex>j \leqslant k : \min(\alpha_j, \beta_j) < \gamma_j</tex>. Из этого следует, что либо <tex>\gamma_j > \alpha_j</tex>, либо <tex>\gamma_j > \beta_j</tex>. Но в первом случае, <tex>q</tex> не окажется делителем <tex>a</tex>, а во втором {{---}} <tex>b</tex>. Значит, делящее два данных числатакого <tex>q</tex> не существует.}} ===Связь с наименьшим общим кратным===

'''Наибольшим Наименьшим общим делителемкратным''' (англ. <tex>\text{lcm}</tex> {{---}} '''НОД'least common multiple'') для двух целых чисел ''m'' <tex>a</tex> и ''n'' <tex>b</tex> называется наибольший из их общих делителейнаименьшее натуральное число, которое делится на <tex>a</tex> и <tex>b</tex> без остатка. Более формально <tex>\text{lcm}(a, b) = \min \left\{ d \mid d \equiv 0 \left( \bmod a\right), d \equiv 0 \left( \bmod b\right) \right\}</tex>}}Существует представление НОК через [[Разложение_на_множители_(факторизация) | разложение числа на простые множители]]:{{Утверждение|id=l002|statement=Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа. Тогда <tex dpi="140">\text{lcm}(a, b) = p_1^{\max(\alpha_1, \beta_1)}\cdot p_2^{\max(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\max(\alpha_k, \beta_k)}</tex>|proof=Доказательство полностью аналогично доказательству [[#l001 | утверждения о НОД]], с той лишь разницей, что мы заменяем <tex>\min</tex> на <tex>\max</tex>, а знаки неравенств {{---}} на противоположные.}} Наибольший общий делитель связан с наименьшим общим кратным следующим равенством: {{Лемма|id=l01|statement=Пусть <tex>a</tex> и <tex>b</tex> {{---}} целые числа. Тогда <tex>\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b</tex>.|proof=По [[#l001 | утверждению о НОД]] и [[#l002 | утверждению о НОК]], пользуясь тем, что <tex>\max(\alpha, \beta) + \min(\alpha, \beta) = \alpha + \beta</tex>, получаем нашу лемму.

Понятие наибольшего общего делителя естественным образом обобщается В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на наборы из более чем двух целых чиселпростые множители.

<font color="darkgreen">// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex> // <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex> // <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex> // <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font> '''function''' naiveGcd(p, q, <tex>\alpha</tex>, <tex>\beta</tex>): gcd <tex>\leftarrow</tex> 1 i, j <tex>\leftarrow</tex> 0, 0 '''while''' i < p.length() '''and''' j < q.length(): '''if''' <tex>p_i</tex> =Алгоритм Евклида=<tex> q_j</tex> : t <tex>\leftarrow</tex> min(<tex>\alpha_i</tex>, <tex>\beta_i</tex>) gcd =gcd <tex>\cdot</tex> <tex>p_i^t</tex> '''else if''' <tex>p_i</tex> < <tex>q_j</tex> : i += 1 '''else''': j += 1 '''return''' gcd Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (<tex>p</tex> и <tex>q</tex>), только результат записывает не в массив, а агрегирует в переменной <tex>\gcd</tex>. Асимптотика равна минимуму из длин массивов <tex>p</tex> и <tex>q</tex>.

: <tex>a = bq_0 b \cdot q_0 + r_1</tex>: <tex>b = r_1q_1 r_1 \cdot q_1 + r_2</tex>: <tex>r_1 = r_2q_2 r_2 \cdot q_2 + r_3</tex>

: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>

: <tex>r_{n-1} = r_n \cdot q_n</tex>

Тогда НОД<tex>\gcd(''a'',''b''), наибольший общий делитель <tex>a</tex> и <tex>b</tex>, равен<tex>= r_n</tex>, последнему ненулевому члену {{---}} последний ненулевой член этой последовательности.}}'''Существование''' таких <tex>r_1, r_2, ...\cdots</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.

* {{Лемма|id=l1|statement=Пусть <tex>a = bq b\cdot q + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex>{{Hider| title = '''Доказательство'''| hidden = 0 | title-style = text-align: left; height: auto; | content-style = text-align: left; | content proof=# Пусть <tex> k </tex> — любой общий делитель чисел <tex> a </tex> и <tex> b</tex>, не обязательно максимальный, тогда <tex> a = t_1 * \cdot k </tex> ; <tex> b = t_2 * \cdot k; </tex> ; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> b </tex> и <tex> r</tex>, так как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>r = a - bq b \cdot q = (t_1 - t_2*\cdot q)*\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> k </tex> делит <tex> r </tex> без остатка)# Обратное также верно и доказывается аналогично 2) - : пусть <tex> k </tex> — любой общий делитель чисел <tex> b </tex> и <tex> r </tex>, не обязательно максимальный, тогда <tex> b = t_1 \cdot k </tex> ; <tex> r = t_2 \cdot k </tex>; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> a </tex> и <tex> b </tex>, так же является делителем как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>a и = b.\cdot q + r = (t_1 \cdot q + t_2)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> a </tex> делит <tex> a </tex> без остатка)# Следовательно, все общие делители пар чисел <tex> a</tex>,<tex> b </tex> и <tex> b</tex>,<tex> r </tex> совпадают. Другими словами, нет общего делителя у чисел <tex> a</tex>,<tex> b</tex>, который не был бы также делителем <tex> b</tex>,<tex> r</tex>, и наоборот.

* {{Лемма|id=l2|statement=<tex>\gcd (0,r) = r</tex> для любого ненулевого <tex>r.</tex>}}Далее, оценим асимптотику работы алгоритма.{{Теорема|statement=Алгоритм Евклида работает за <tex>O(\log \min (a, b))</tex> }}Доказательство этого факта<ref>[http://mathworld.wolfram.com/EuclideanAlgorithm.html Wolfram MathWorld {{---}} алгоритм Евклида]</ref> достаточно громоздкое, поэтому не будем приводить его здесь.

===Расширенный Таким образом, реализация стандартного алгоритма Евклида, достаточно проста: '''function''' euclideanGcd(a, b) : '''while''' b <tex>\neq</tex> 0 : t <tex>\leftarrow</tex> b b <tex>\leftarrow</tex> a mod b a <tex>\leftarrow</tex> t '''return''' aМы получили очень простой алгоритм Евклида===, который считает НОД за логарифмическое время. However, we can do better.

Формулы для <tex>r_i</tex> могут быть переписаны следующим образом===Двоичный алгоритм Евклида===Идея улучшения:давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.

Для начала, опишем еще несколько свойств <tex>gcd</tex>: {{Утверждение|id=l3|statement=Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда* <tex>r_1 \gcd(2 \cdot a, 2 \cdot b) = 2 \cdot \gcd(a + , b(-q_0)</tex>: * <tex>r_2= \gcd(2 \cdot a, 2 \cdot b - r_1q_1 + 1) = \gcd(a, 2 \cdot b + 1)</tex>* <tex>\gcd(-q_1)2 \cdot a +1, 2 \cdot b+ 1) = \gcd(\left|a - b\right|, 2 \cdot b + 1+q_1q_0)</tex>|proof=Тривиальным образом следует из определения}}Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости): '''function''' binaryGcd(a, b) : '''if''' a == b '''or''' b == 0 : '''return''' a '''if''' a == 0 : '''return''' b <texfont color="darkgreen">\cdots// первые два случая</texfont> '''if''' a mod 2 = 0 : '''if''' b mod 2 = 0 : '''return''' binaryGcd(a / 2, b / 2) <tex>\gcd cdot</tex> 2 '''else''' '''return''' binaryGcd(a/ 2,b) <font color= r_n = as + bt"darkgreen">// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font>здесь ''s'if' и ''tb mod 2 = 0 : '' целые. Это представление наибольшего общего делителя называется 'return''соотношением Безу' binaryGcd(a, b / 2) <font color="darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex> // поэтому давайте всегда оставлять меньшее</font> ''', а числа if'''sa > b : '' и 'return't'' — binaryGcd((a - b) / 2, b) '''коэффициентами Безуreturn'''. Соотношение Безу является ключевым в доказательстве леммы Евклида binaryGcd((b - a) / 2, a) Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и основной теоремы арифметики[[#l2 | о НОДе нуля]]).

Отношение ===Расширенный алгоритм Евклида===В стандартном алгоритме мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex> такие, что <tex>a \cdot x + b \cdot y = \gcd(a, b)</tex> допускает представление в виде цепной дроби. Пусть мы нашли пару <tex>x_1, y_1: \:b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)</tex>.Очевидно, что <tex>a \bmod b = a - \lfloor \dfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \lfloor \dfrac{a}{b}\frac abrfloor \cdot b\right) \cdot y_1 =[q_0; q_1b \cdot \left(x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right) + a \cdot y_1 = a \cdot y_1 + b \cdot \left(x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right)</tex>. Следовательно, q_2приходим к расширенному алгоритму Евклида: <font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font> '''function''' extendedGcd(a, b) : '''if''' b == 0 : '''return''' a, 1, 0 gcd,<tex>x_1</tex>, <tex>y_1</tex> <tex>\leftarrow</tex> extendedGcd(b, a mod b) x <tex>\leftarrow</tex> <tex>y_1</tex> y <tex>\cdotsleftarrow</tex> <tex>x_1</tex> - (a div b) <tex>\cdot</tex> <tex>y_1</tex> '''return''' gcd, <tex>x</tex>,q_n]<tex>y</tex>Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа <tex>x</tex> и <tex>y</tex> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу <tex>t/s</tex>, взятому со знаком минус:== См. также==: <tex>* [[q_0; q_1, q_2,\cdots,q_{n-1}Разложение_на_множители_(факторизация) | Разложение на множители]]* [[Простые_числа | Простые числа]]* [[Основная_теорема_арифметики | Основная теорема арифметики]] = -\frac ts</tex>.

==Наибольший общий делитель как общий делитель, делящий все остальные общие остальные общие делителиПримечания==<references />[[Категория: Теория чисел]]

==Источники информации==* [https://en.wikipedia.org/wiki/Greatest_common_divisor Wikipedia {{---}} Greatest common divisor]* [Категорияhttps: Классы чисел]//en.wikipedia.org/wiki/Binary_GCD_algorithm Wikipedia {{---}} Binary GCD Algorithm]