Изменения
→Расширенный алгоритм Евклида
{{Определение
|definition=
'''Наибольшим общим делителем''' (англ. <tex>\gcd</tex> {{---}} ''greatest common divisor'') для двух целых чисел <tex>ma</tex> и <tex>nb</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>
}}
|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}, \:
|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>, а знаки неравенств {{---}} на противоположные.
В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на простые множители.
<font color=green"darkgreen">// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex></font> <font color=green>// <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex></font> <font color=green>// <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex></font> <font color=green>// <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font> '''function''' <tex>\mathtt{naiveGcd}(p, q, <tex>\alpha</tex>, <tex>\beta):</tex>): gcd <tex>\mathtt{gcd} \leftarrow 1</tex>1 i, j <tex>\mathtt{i, j} \leftarrow 0, 0</tex>0, 0 '''while''' <tex>\mathtt{i} < p\mathtt{.length()}</tex> '''and''' <tex>\mathtt{j} < q\mathtt{.length()}:</tex> '''if''' <tex>p_i</tex> == <tex> q_j:</tex>: t <tex>\mathtt{t} \leftarrow \</tex> min(<tex>\alpha_i</tex>, <tex>\beta_j)beta_i</tex>) gcd = gcd <tex>\mathtt{gcd} = \mathtt{gcd} \cdot </tex> <tex>p_i^{\mathtt{t}}</tex> '''else if''' <tex>p_i < /tex> < <tex>q_j:</tex>: <tex>\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
'''else''':
Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (<tex>p</tex> и <tex>q</tex>), только результат записывает не в массив, а агрегирует в переменной <tex>\gcd</tex>. Асимптотика равна минимуму из длин массивов <tex>p</tex> и <tex>q</tex>.
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
определена тем, что каждое <tex>r_k</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>\cdots</tex>
: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>
: <tex>\cdots</tex>
: <tex>r_{n-1} = r_n \cdot q_n</tex>
Тогда <tex>\gcd(a, b) = 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>|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>, и наоборот.
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
}}
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
'''function''' <tex>\mathtt{euclideanGcd}(\mathtt{a, b}):</tex> '''while''' b <tex>\mathtt{b} \neq 0:</tex>0 : t <tex>\mathtt{t} \leftarrow \mathtt{b}</tex>b b <tex>\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}</tex>a mod b a <tex>\mathtt{a} \leftarrow \mathtt{t}</tex>t '''return''' <tex>\mathtt{a}</tex>
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
|id=l3
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - — натуральные числа, тогда* <tex>\gcd(2a2 \cdot a, 2b2 \cdot b) = 2\cdot\gcd(a, b)</tex>* <tex>\gcd(2a2 \cdot a, 2b 2 \cdot b + 1) = \gcd(a, 2b 2 \cdot b + 1)</tex>* <tex>\gcd(2a 2 \cdot a + 1, 2b 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2b 2 \cdot b + 1)</tex>
|proof=
Тривиальным образом следует из определения
}}
Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):
'''function''' <tex>\mathtt{binaryGcd(a, b)}:</tex> '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{b}</tex> '''or''' <tex>\mathtt{b}</tex> == <tex>\mathtt{0}:</tex> '''return''' <tex>\mathtt{a}</tex> '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{0}:</tex> '''return''' <tex>\mathtt{b}</tex> <font color=green"darkgreen">// первые два случая</font> '''if''' <tex>\mathtt{a} \bmod mod 2 = 0:</tex> '''if''' <tex>\mathtt{b} \bmod mod 2 = 0:</tex> '''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b\: /\: 2)} <tex>\cdot 2</tex>2
'''else'''
'''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b)}</tex> <font color=green"darkgreen">// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font> '''if''' <tex>\mathtt{b} \bmod mod 2 = 0:</tex> '''return''' <tex>\mathtt{binaryGcd(a, b\: /\: 2)}</tex> <font color=green"darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex></font> <font color=green>// поэтому давайте всегда оставлять меньшее</font> '''if''' <tex>\mathtt{a} > \mathtt{b}:</tex> '''return''' <tex>\mathtt{binaryGcd((a - b)\: /\: 2, b)}</tex> '''return''' <tex>\mathtt{binaryGcd((b - a)\: /\: 2, a)}</tex>
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
===Расширенный алгоритм Евклида===
В стандартном алгоритме, мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex> такие, что <tex>ax a \cdot x + by b \cdot y = \gcd(a, b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: bx_1 b \cdot x_1 + (a \bmod b)\cdot y_1 = \gcd(a, b)</tex>.Очевидно, что <tex>a \bmod b = a - \lfloor \fracdfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>bx_1 b \cdot x_1 + (a \bmod b)\cdot y_1 = b \cdot x_1 + \left(a - \lfloor \fracdfrac{a}{b}\rfloor \cdot b\right)\cdot y_1 = b\cdot \left(x_1 - \lfloor \fracdfrac{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>. Следовательно, приходим к расширенному алгоритму Евклида:
<font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font>
'''function''' <tex>\mathtt{extendedGcd(a, b)}:</tex> '''if''' <tex>\mathtt{b} == 0:</tex> '''return''' <tex>\mathtt{a}, 1, 0 gcd, 1<tex>x_1</tex> , <tex>\mathtt{gcd, x_1, y_1} </tex> <tex>\leftarrow \mathtt{</tex> extendedGcd(b, a} \bmod \mathtt{mod b)} x <tex>\leftarrow</tex> <tex>\mathtt{x} \leftarrow \mathtt{y_1}</tex> y <tex>\mathtt{y} \leftarrow \mathtt{</tex> <tex>x_1} </tex> - (\mathtt{a} \text{ div } \mathtt{b}) <tex>\cdot \mathtt{</tex> <tex>y_1}</tex> '''return''' gcd, <tex>\mathtt{gcd, x</tex>, <tex>y}</tex>
Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа <tex>x</tex> и <tex>y</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]
