Изменения

{{В разработкеОпределение|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> не существует.}} ===Связь с наименьшим общим кратным=== {{Определение|definition='''Наименьшим общим кратным''' (англ. <tex>\text{lcm}</tex> {{---}} ''least common multiple'') для двух чисел <tex>a</tex> и <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

Пусть Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (<mathtex>ap</mathtex> и <mathtex>bq</mathtex> — целые числа), только результат записывает не равные одновременно нулю, и последовательность чисел: <math> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math>определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущеев массив, а предпоследнее делится на последнее нацело, то есть: агрегирует в переменной <math>a = bq_0 + r_1</math>: <math>b = r_1q_1 + r_2</math>: <math>r_1 = r_2q_2 + r_3</math>: <mathtex>\cdotsgcd</mathtex>: . Асимптотика равна минимуму из длин массивов <mathtex>r_{k-2} = r_{k-1} q_{k-1} + r_kp</mathtex>: <math>\cdots</math>: и <mathtex>r_{n-1} = r_n q_nq</mathtex>.

Тогда НОД(''===Стандартный алгоритм Евклида==={{Теорема|statement=Пусть <tex>a</tex> и <tex>b</tex> — целые числа, не равные одновременно нулю, и последовательность чисел: <tex> a'',''\, b''), наибольший общий делитель \,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть: <mathtex>a= b \cdot q_0 + r_1</mathtex> и : <mathtex>b= r_1 \cdot q_1 + r_2</tex>: <tex>r_1 = r_2 \cdot q_2 + r_3</tex>: <tex>\cdots</tex>: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</mathtex>: <tex>\cdots</tex>, равен: <mathtex>r_{n-1} = r_n\cdot q_n</mathtex>, последнему ненулевому члену этой последовательности.

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

* {{Лемма|id=l1|statement=Пусть <mathtex>a = bq b\cdot q + r</mathtex>, тогда <mathtex>\gcd (a,b) = \gcd (b,r).</mathtex>{{Hider| title = '''Доказательство'''| hidden = 0 | title-style = text-align: left; height: auto; | content-style proof= text-align: left; | content =# Пусть <tex> k </tex> — любой общий делитель чисел <tex> a </tex> и <tex> b</tex>, не обязательно максимальный, тогда <mathtex> a = t_1 * \cdot k </mathtex> ; <mathtex> b = t_2 * \cdot k; </mathtex> ; где <mathtex> t_1 </mathtex> и <mathtex> t_2 </mathtex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> b </tex> и <tex> r</tex>, так как <tex> b </tex> делится на <tex> k </tex> по определению, а <mathtex>r = a - bq b \cdot q = (t_1 - t_2*\cdot q)*\cdot k </mathtex> (выражение в скобках есть целое число, следовательно, <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=<mathtex>\gcd (0,r) = r</mathtex> для любого ненулевого <mathtex>r.</mathtex>}}Далее, оценим асимптотику работы алгоритма.{{Теорема|statement=Алгоритм Евклида работает за <tex>O(\log \min (a, b))</tex> }}Доказательство этого факта<ref>[http://mathworld.wolfram.com/EuclideanAlgorithm.html Wolfram MathWorld {{---}} алгоритм Евклида]</ref> достаточно громоздкое, поэтому не будем приводить его здесь. Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

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

===Расширенный Двоичный алгоритм Евклида===Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.

Формулы Для начала, опишем еще несколько свойств <tex>gcd</tex>:{{Утверждение|id=l3|statement=Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда* <tex>\gcd(2 \cdot a, 2 \cdot b) = 2 \cdot \gcd(a, b)</tex>* <tex>\gcd(2 \cdot a, 2 \cdot b + 1) = \gcd(a, 2 \cdot b + 1)</tex>* <tex>\gcd(2 \cdot a + 1, 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2 \cdot b + 1)</tex>|proof=Тривиальным образом следует из определения}}Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости): '''function''' binaryGcd(a, b) : '''if''' a == b '''or''' b == 0 : '''return''' a '''if''' a == 0 : '''return''' b <font color="darkgreen">// первые два случая</font> '''if''' a mod 2 = 0 : '''if''' b mod 2 = 0 : '''return''' binaryGcd(a / 2, b / 2) <tex>\cdot</tex> 2 '''else''' '''return''' binaryGcd(a / 2, b) <font color="darkgreen">// второй случай, только <mathtex>r_ia</mathtex> могут быть переписаны следующим образоми <tex>b</tex> поменяли местами</font> '''if''' b mod 2 = 0 : '''return''' binaryGcd(a, b / 2) <font color="darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex> // поэтому давайте всегда оставлять меньшее</font> '''if''' a > b : '''return''' binaryGcd((a - b) / 2, b) '''return''' binaryGcd((b - a) / 2, a)

: <math>r_1 = a + b(-q_0)</math>: <math>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</math>: <math>\cdots</math>: <math>\gcd Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(a,b) = r_n = as + bt</math>здесь ''s'' это следует из утверждений [[#l3 | о НОДе четных и ''t'' целые. Это представление наибольшего общего делителя называется '''соотношением Безу''', а числа ''s'' нечетных]] и ''t'' — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики[[#l2 | о НОДе нуля]]).

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

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

==Наибольший общий делитель как общий делитель, делящий все остальные общие остальные общие делителиПримечания==<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]