Наибольший общий делитель — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Стандартный алгоритм Евклида)
м (rollbackEdits.php mass rollback)
 
(не показано 68 промежуточных версий 6 участников)
Строка 1: Строка 1:
==Наибольший общий делитель как максимальное число, делящее два данных числа==
+
{{Определение
 +
|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=
 
|definition=
'''Наибольшим общим делителем''' ('''НОД''') для двух целых чисел ''m'' и ''n'' называется наибольший из их общих делителей.
+
'''Наибольший общий делитель''' для целочисленного множества <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>, получаем нашу лемму.
 
}}
 
}}
Пример: для чисел 70 и 105 наибольший общий делитель равен 35.
 
  
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел ''m'' или ''n'' не ноль.
+
==Алгоритм Вычисления==
 +
 
 +
===Наивный алгоритм===
  
Возможные обозначения наибольшего общего делителя чисел ''m'' и ''n'':
+
В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на простые множители.
* НОД(''m'', ''n'')
 
* (''m'', ''n'')
 
* gcd(''m'', ''n'') (от англ. Greatest Common Divisor)
 
  
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.
+
<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>.
  
 
===Стандартный алгоритм Евклида===
 
===Стандартный алгоритм Евклида===
 
+
{{Теорема
 +
|statement=
 
Пусть <tex>a</tex> и <tex>b</tex> — целые числа, не равные одновременно нулю, и последовательность чисел
 
Пусть <tex>a</tex> и <tex>b</tex> — целые числа, не равные одновременно нулю, и последовательность чисел
 
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
 
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
 
определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
 
определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <tex>a = bq_0 + r_1</tex>
+
: <tex>a = b \cdot q_0 + r_1</tex>
: <tex>b = r_1q_1 + r_2</tex>
+
: <tex>b = r_1 \cdot q_1 + r_2</tex>
: <tex>r_1 = r_2q_2 + r_3</tex>
+
: <tex>r_1 = r_2 \cdot q_2 + r_3</tex>
 
: <tex>\cdots</tex>
 
: <tex>\cdots</tex>
: <tex>r_{k-2} = r_{k-1} q_{k-1} + r_k</tex>
+
: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>
 
: <tex>\cdots</tex>
 
: <tex>\cdots</tex>
: <tex>r_{n-1} = r_n q_n</tex>
+
: <tex>r_{n-1} = r_n \cdot q_n</tex>
  
Тогда НОД(''a'',''b''), наибольший общий делитель <tex>a</tex> и <tex>b</tex>, равен
+
Тогда <tex>\gcd(a, b) = r_n</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''.
'''Существование''' таких <tex>r_1, r_2, ...</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.
 
  
 
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
 
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
 
{{Лемма
 
{{Лемма
 
|id=l1
 
|id=l1
|statement=Пусть <tex>a = bq + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex>
+
|statement=Пусть <tex>a = b\cdot q + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex>
|proof=Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <tex> a = t_1 k </tex> ; <tex> b = t_2 k; </tex> где <tex> t_1 </tex> и <tex> t_2 </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> — целые числа из определения.
# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <tex>r = a - bq = (t_1 - t_2 q)k </tex> (выражение в скобках есть целое число, следовательно, k делит r без остатка)
+
# Тогда <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> без остатка)
# Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
+
# Обратное также верно и доказывается аналогично: пусть  <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> — целые числа из определения.
# Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
+
# Тогда <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>\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> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
 
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <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
 +
    <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">// второй случай, только <tex>a</tex> и <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)
  
Формулы для <tex>r_i</tex> могут быть переписаны следующим образом:
+
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
  
: <tex>r_1 = a + b(-q_0)</tex>
+
Можно показать<ref>http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm</ref>, что этот алгоритм, в среднем на 60% более эффективен, чем классический.
: <tex>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</tex>
 
: <tex>\cdots</tex>
 
: <tex>\gcd (a,b) = r_n = as + bt</tex>
 
здесь ''s'' и ''t'' целые. Это представление наибольшего общего делителя называется '''соотношением Безу''', а числа ''s'' и ''t'' — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
 
  
==== Связь с цепными дробями ====
+
===Расширенный алгоритм Евклида===
 +
В стандартном алгоритме мы использовали следующее свойство: <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>. Следовательно, приходим к расширенному алгоритму Евклида:
 +
<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>\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> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
  
Отношение <tex>a/b</tex> допускает представление в виде цепной дроби:
+
== См. также==
: <tex>\frac ab=[q_0; q_1, q_2,\cdots,q_n]</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]

Текущая версия на 19:20, 4 сентября 2022

Определение:
Наибольшим общим делителем (англ. [math]\gcd[/math]greatest common divisor) для двух целых чисел [math]a[/math] и [math]b[/math] называется наибольшее натуральное [math]d[/math], такое что [math]a[/math] делится на [math]d[/math] и [math]b[/math] делится на [math]d[/math]. Более формально, [math]\gcd(a, b) =\max \left\{ d \mid a \equiv 0 \left(\bmod d\right), b \equiv 0 \left(\bmod d\right) \right\}[/math]


Свойства НОД

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел [math]m[/math] или [math]n[/math] не ноль.

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


Определение:
Наибольший общий делитель для целочисленного множества [math]A[/math] определяется как [math]\gcd(A) = \max \left\{ d \mid \forall a_j \in A,\: a_j \equiv 0 \left(\bmod d \right)\right\}[/math]


Существует определение НОД через разложение числа на простые множители:

Утверждение:
Пусть [math]a[/math] и [math]b[/math] — натуральные числа. Тогда [math]\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)},[/math] где [math]p_j[/math] — делитель [math]a[/math] и [math]b[/math]. (Если [math]a[/math] не делится на [math]p_j,[/math] будем считать, что [math]p_j[/math] присутствует в разложении [math]a[/math] в [math]0[/math]-ой степени.)
[math]\triangleright[/math]

Разложим [math]a[/math] и [math]b[/math] на множители: пусть [math]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}[/math], где [math]p_j, q_j[/math] — простые, а [math]\alpha_j, \beta_j[/math] — натуральные (такие разложения существуют, по основной теореме арифметики). Без ограничения общности, можно считать, что [math]p_j = q_j, k = n[/math] (если это не так, сделаем соответствующие [math]\alpha[/math] и [math]\beta[/math] равными нулю). Очевидно, что в таком случае [math]a[/math] и на [math]b[/math] делятся на [math]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)} [/math]. Проверим его максимальность. Пусть существует [math]q \gt p[/math], такое что [math]a[/math] и [math]b[/math] делятся на [math]q[/math]. Тогда оно необходимо будет раскладываться на те же простые множители, что и [math]p[/math].

Пусть [math]q = p_1^{\gamma_1}\cdot p_2^{\gamma_2} \cdot \dotso \cdot p_k^{\gamma_k} [/math]. Значит, существует [math]j \leqslant k : \min(\alpha_j, \beta_j) \lt \gamma_j[/math]. Из этого следует, что либо [math]\gamma_j \gt \alpha_j[/math], либо [math]\gamma_j \gt \beta_j[/math]. Но в первом случае, [math]q[/math] не окажется делителем [math]a[/math], а во втором — [math]b[/math]. Значит, такого [math]q[/math] не существует.
[math]\triangleleft[/math]

Связь с наименьшим общим кратным

Определение:
Наименьшим общим кратным (англ. [math]\text{lcm}[/math]least common multiple) для двух чисел [math]a[/math] и [math]b[/math] называется наименьшее натуральное число, которое делится на [math]a[/math] и [math]b[/math] без остатка. Более формально [math]\text{lcm}(a, b) = \min \left\{ d \mid d \equiv 0 \left( \bmod a\right), d \equiv 0 \left( \bmod b\right) \right\}[/math]

Существует представление НОК через разложение числа на простые множители:

Утверждение:
Пусть [math]a[/math] и [math]b[/math] — натуральные числа. Тогда [math]\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)}[/math]
[math]\triangleright[/math]
Доказательство полностью аналогично доказательству утверждения о НОД, с той лишь разницей, что мы заменяем [math]\min[/math] на [math]\max[/math], а знаки неравенств — на противоположные.
[math]\triangleleft[/math]

Наибольший общий делитель связан с наименьшим общим кратным следующим равенством:

Лемма:
Пусть [math]a[/math] и [math]b[/math] — целые числа. Тогда [math]\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b[/math].
Доказательство:
[math]\triangleright[/math]
По утверждению о НОД и утверждению о НОК, пользуясь тем, что [math]\max(\alpha, \beta) + \min(\alpha, \beta) = \alpha + \beta[/math], получаем нашу лемму.
[math]\triangleleft[/math]

Алгоритм Вычисления

Наивный алгоритм

В наивном методе, мы считаем, что нам известны разложения чисел [math]a[/math] и [math]b[/math] на простые множители.

// [math]p[/math] — множество простых чисел в разложении [math]a[/math]
// [math]q[/math] — множество простых чисел в разложении [math]b[/math]
// [math]\alpha[/math] — степени простых чисел в разложении [math]a[/math]
// [math]\beta[/math] — степени простых чисел в разложении [math]b[/math]
function naiveGcd(p, q, [math]\alpha[/math], [math]\beta[/math]): 
    gcd [math]\leftarrow[/math] 1
    i, j [math]\leftarrow[/math] 0, 0
    while i < p.length() and j < q.length():
        if [math]p_i[/math] == [math] q_j[/math] : 
        t [math]\leftarrow[/math] min([math]\alpha_i[/math], [math]\beta_i[/math])
            gcd = gcd [math]\cdot[/math] [math]p_i^t[/math]
        else if [math]p_i[/math] < [math]q_j[/math] :
            i += 1
        else:
            j += 1
    return gcd

Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов ([math]p[/math] и [math]q[/math]), только результат записывает не в массив, а агрегирует в переменной [math]\gcd[/math]. Асимптотика равна минимуму из длин массивов [math]p[/math] и [math]q[/math].

Стандартный алгоритм Евклида

Теорема:
Пусть [math]a[/math] и [math]b[/math] — целые числа, не равные одновременно нулю, и последовательность чисел
[math] a,\, b,\,r_1 \gt r_2 \gt r_3 \gt r_4 \gt \cdots \gt r_n[/math]

определена тем, что каждое [math]r_k[/math] — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

[math]a = b \cdot q_0 + r_1[/math]
[math]b = r_1 \cdot q_1 + r_2[/math]
[math]r_1 = r_2 \cdot q_2 + r_3[/math]
[math]\cdots[/math]
[math]r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k[/math]
[math]\cdots[/math]
[math]r_{n-1} = r_n \cdot q_n[/math]
Тогда [math]\gcd(a, b) = r_n[/math] — последний ненулевой член этой последовательности.

Существование таких [math]r_1, r_2, \cdots[/math], то есть возможность деления с остатком [math]m[/math] на [math]n[/math] для любого целого [math]m[/math] и целого [math]n\ne 0[/math], доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Лемма:
Пусть [math]a = b\cdot q + r[/math], тогда [math]\gcd (a,b) = \gcd (b,r).[/math]
Доказательство:
[math]\triangleright[/math]
  1. Пусть [math] k [/math] — любой общий делитель чисел [math] a [/math] и [math] b [/math], не обязательно максимальный, тогда [math] a = t_1 \cdot k [/math] ; [math] b = t_2 \cdot k [/math]; где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.
  2. Тогда [math] k [/math] также общий делитель чисел [math] b [/math] и [math] r [/math], так как [math] b [/math] делится на [math] k [/math] по определению, а [math]r = a - b \cdot q = (t_1 - t_2 \cdot q)\cdot k [/math] (выражение в скобках есть целое число, следовательно, [math] k [/math] делит [math] r [/math] без остатка)
  3. Обратное также верно и доказывается аналогично: пусть [math] k [/math] — любой общий делитель чисел [math] b [/math] и [math] r [/math], не обязательно максимальный, тогда [math] b = t_1 \cdot k [/math] ; [math] r = t_2 \cdot k [/math]; где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.
  4. Тогда [math] k [/math] также общий делитель чисел [math] a [/math] и [math] b [/math], так как [math] b [/math] делится на [math] k [/math] по определению, а [math]a = b \cdot q + r = (t_1 \cdot q + t_2)\cdot k [/math] (выражение в скобках есть целое число, следовательно, [math] a [/math] делит [math] a [/math] без остатка)
  5. Следовательно, все общие делители пар чисел [math] a [/math], [math] b [/math] и [math] b [/math], [math] r [/math] совпадают. Другими словами, нет общего делителя у чисел [math] a [/math], [math] b [/math], который не был бы также делителем [math] b [/math], [math] r [/math], и наоборот.
  6. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
[math]\triangleleft[/math]
Лемма:
[math]\gcd (0,r) = r[/math] для любого ненулевого [math]r.[/math]

Далее, оценим асимптотику работы алгоритма.

Теорема:
Алгоритм Евклида работает за [math]O(\log \min (a, b))[/math]

Доказательство этого факта[1] достаточно громоздкое, поэтому не будем приводить его здесь.

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

Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:

function euclideanGcd(a, b) :
    while b [math]\neq[/math] 0 :
        t [math]\leftarrow[/math] b
        b [math]\leftarrow[/math] a mod b
        a [math]\leftarrow[/math] t
    return a

Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.

Двоичный алгоритм Евклида

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

Для начала, опишем еще несколько свойств [math]gcd[/math]:

Утверждение:
Пусть [math]a[/math] и [math]b[/math] — натуральные числа, тогда
  • [math]\gcd(2 \cdot a, 2 \cdot b) = 2 \cdot \gcd(a, b)[/math]
  • [math]\gcd(2 \cdot a, 2 \cdot b + 1) = \gcd(a, 2 \cdot b + 1)[/math]
  • [math]\gcd(2 \cdot a + 1, 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2 \cdot b + 1)[/math]
[math]\triangleright[/math]
Тривиальным образом следует из определения
[math]\triangleleft[/math]

Пользуясь этим, и утверждением о НОДе нуля, определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):

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) [math]\cdot[/math] 2
        else
            return binaryGcd(a / 2, b)
    // второй случай, только [math]a[/math] и [math]b[/math] поменяли местами
    if b mod 2 = 0 : 
        return binaryGcd(a, b / 2)
    // остается третий случай. На самом деле, мы можем оставлять справа и [math]a[/math], и [math]b[/math]
    // поэтому давайте всегда оставлять меньшее
    if a > b : 
        return binaryGcd((a - b) / 2, b)
    return binaryGcd((b - a) / 2, a)

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

Можно показать[2], что этот алгоритм, в среднем на 60% более эффективен, чем классический.

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

В стандартном алгоритме мы использовали следующее свойство: [math]\gcd(a, b) = \gcd(b, a \bmod b)[/math]. Воспользуемся им для того, чтобы решить следующую задачу: найти [math]x[/math] и [math]y[/math] такие, что [math]a \cdot x + b \cdot y = \gcd(a, b)[/math]. Пусть мы нашли пару [math]x_1, y_1: \: b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)[/math]. Очевидно, что [math]a \bmod b = a - \lfloor \dfrac{a}{b}\rfloor \cdot b[/math]. Получаем: [math]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)[/math]. Следовательно, приходим к расширенному алгоритму Евклида:

// Алгоритм возвращает тройку [math]\gcd, x, y[/math]
function extendedGcd(a, b) : 
    if b == 0 : 
        return a, 1, 0
    gcd, [math]x_1[/math], [math]y_1[/math] [math]\leftarrow[/math] extendedGcd(b, a mod b)
    x [math]\leftarrow[/math] [math]y_1[/math]
    y [math]\leftarrow[/math] [math]x_1[/math] - (a div b) [math]\cdot[/math] [math]y_1[/math]
    return gcd, [math]x[/math], [math]y[/math]

Такое представление наибольшего общего делителя называется соотношением Безу, а числа [math]x[/math] и [math]y[/math]коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

См. также

Примечания

Источники информации