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

2021-05-06T14:17:12Z

188.65.244.35: /* Расширенный алгоритм Евклида */

{{Определение
|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> на простые множители.

// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex>
// <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex>
// <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex>
// <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex>
'''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>.

===Стандартный алгоритм Евклида===
{{Теорема
|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> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <tex>a = b \cdot q_0 + r_1</tex>
: <tex>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</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 = 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 - b \cdot q = (t_1 - t_2 \cdot q)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> k </tex> делит <tex> r </tex> без остатка)
# Обратное также верно и доказывается аналогично: пусть <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> достаточно громоздкое, поэтому не будем приводить его здесь.

Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
'''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>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
// первые два случая
'''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)
// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами
'''if''' b mod 2 = 0 :
'''return''' binaryGcd(a, b / 2)
// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex>
// поэтому давайте всегда оставлять меньшее
'''if''' a > b :
'''return''' binaryGcd((a - b) / 2, b)
'''return''' binaryGcd((b - a) / 2, a)

Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).

Можно показать<ref>http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm</ref>, что этот алгоритм, в среднем на 60% более эффективен, чем классический.

===Расширенный алгоритм Евклида===
В стандартном алгоритме мы использовали следующее свойство: <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}\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>. Следовательно, приходим к расширенному алгоритму Евклида:
// Алгоритм возвращает тройку <tex>\gcd, x, y</tex>
'''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>\leftarrow</tex> <tex>x_1</tex> - (a div b) <tex>\cdot</tex> <tex>y_1</tex>
'''return''' gcd, <tex>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]

Викиконспекты - Вклад участника [ru]

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