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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Расширенный алгоритм Евклида)
(не показано 29 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Наибольшим общим делителем''' (англ. <tex>\gcd</tex> {{---}} ''greatest common divisor'') для двух целых чисел <tex>m</tex> и <tex>n</tex> называется наибольшее натуральное <tex>d</tex>, такое что <tex>a</tex> делится на <tex>d</tex> и <tex>b</tex> делится на <tex>d</tex>. Более формально,  
+
'''Наибольшим общим делителем''' (англ. <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>\gcd(a, b) =\max \left\{ d \mid a \equiv 0 \left(\bmod d\right), b \equiv 0 \left(\bmod d\right) \right\}</tex>
 
}}
 
}}
Строка 22: Строка 22:
 
|id=l001
 
|id=l001
 
|statement=
 
|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>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=
 
|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}, \:  
 
Разложим <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}, \:  
Строка 43: Строка 43:
 
|id=l002
 
|id=l002
 
|statement=
 
|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>
+
Пусть <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=
 
|proof=
 
Доказательство полностью аналогично доказательству [[#l001 | утверждения о НОД]], с той лишь разницей, что мы заменяем <tex>\min</tex> на <tex>\max</tex>, а знаки неравенств {{---}} на противоположные.
 
Доказательство полностью аналогично доказательству [[#l001 | утверждения о НОД]], с той лишь разницей, что мы заменяем <tex>\min</tex> на <tex>\max</tex>, а знаки неравенств {{---}} на противоположные.
Строка 63: Строка 63:
  
 
В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на простые множители.
 
В наивном методе, мы считаем, что нам известны разложения чисел <tex>a</tex> и <tex>b</tex> на простые множители.
  <font color=green>// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex></font>
+
 
  <font color=green>// <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex></font>
+
  <font color="darkgreen">// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex>
  <font color=green>// <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex></font>
+
  // <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex>
  <font color=green>// <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font>
+
  // <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex>
  '''function''' <tex>\mathtt{naiveGcd}(p, q, \alpha, \beta):</tex>
+
  // <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font>
     <tex>\mathtt{gcd} \leftarrow 1</tex>
+
  '''function''' naiveGcd(p, q, <tex>\alpha</tex>, <tex>\beta</tex>):
     <tex>\mathtt{i, j} \leftarrow 0, 0</tex>
+
     gcd <tex>\leftarrow</tex> 1
     '''while''' <tex>\mathtt{i} < p\mathtt{.length()}</tex> '''and''' <tex>\mathtt{j} < q\mathtt{.length()}:</tex>
+
     i, j <tex>\leftarrow</tex> 0, 0
         '''if''' <tex>p_i</tex> == <tex> q_j:</tex>
+
     '''while''' i < p.length() '''and''' j < q.length():
            <tex>\mathtt{t} \leftarrow \min(\alpha_i, \beta_j)</tex>
+
         '''if''' <tex>p_i</tex> == <tex> q_j</tex> :
             <tex>\mathtt{gcd} = \mathtt{gcd} \cdot p_i^{\mathtt{t}}</tex>
+
        t <tex>\leftarrow</tex> min(<tex>\alpha_i</tex>, <tex>\beta_i</tex>)
         '''else if''' <tex>p_i < q_j:</tex>
+
             gcd = gcd <tex>\cdot</tex> <tex>p_i^t</tex>
             <tex>\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
+
         '''else if''' <tex>p_i</tex> < <tex>q_j</tex> :
 +
             i += 1
 
         '''else''':
 
         '''else''':
             <tex>\mathtt{j} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>
+
             j += 1
     '''return''' <tex>\mathtt{gcd}</tex>
+
     '''return''' gcd
  
 
Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (<tex>p</tex> и <tex>q</tex>), только результат записывает не в массив, а агрегирует в переменной <tex>\gcd</tex>. Асимптотика равна минимуму из длин массивов <tex>p</tex> и <tex>q</tex>.
 
Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (<tex>p</tex> и <tex>q</tex>), только результат записывает не в массив, а агрегирует в переменной <tex>\gcd</tex>. Асимптотика равна минимуму из длин массивов <tex>p</tex> и <tex>q</tex>.
Строка 88: Строка 89:
 
: <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>
  
Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последнему ненулевому члену этой последовательности.
+
Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последний ненулевой член этой последовательности.
 
}}
 
}}
'''Существование''' таких <tex>r_1, r_2, ...</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.
+
'''Существование''' таких <tex>r_1, r_2, \cdots</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>, и наоборот.
 
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
 
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
 
}}
 
}}
Строка 124: Строка 126:
  
 
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
 
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
  '''function''' <tex>\mathtt{euclideanGcd}(\mathtt{a, b}):</tex>
+
  '''function''' euclideanGcd(a, b) :
     '''while''' <tex>\mathtt{b} \neq 0:</tex>
+
     '''while''' b <tex>\neq</tex> 0 :
         <tex>\mathtt{t} \leftarrow \mathtt{b}</tex>
+
         t <tex>\leftarrow</tex> b
         <tex>\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}</tex>
+
         b <tex>\leftarrow</tex> a mod b
         <tex>\mathtt{a} \leftarrow \mathtt{t}</tex>
+
         a <tex>\leftarrow</tex> t
     '''return''' <tex>\mathtt{a}</tex>
+
     '''return''' a
 
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
 
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
  
Строка 139: Строка 141:
 
|id=l3
 
|id=l3
 
|statement=
 
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа, тогда
+
Пусть <tex>a</tex> и <tex>b</tex> натуральные числа, тогда
* <tex>\gcd(2a, 2b) = 2\cdot\gcd(a, b)</tex>
+
* <tex>\gcd(2 \cdot a, 2 \cdot b) = 2 \cdot \gcd(a, b)</tex>
* <tex>\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)</tex>
+
* <tex>\gcd(2 \cdot a, 2 \cdot b + 1) = \gcd(a, 2 \cdot b + 1)</tex>
* <tex>\gcd(2a + 1, 2b + 1) = \gcd(\left|a - b\right|, 2b + 1)</tex>
+
* <tex>\gcd(2 \cdot a + 1, 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2 \cdot b + 1)</tex>
 
|proof=
 
|proof=
 
Тривиальным образом следует из определения
 
Тривиальным образом следует из определения
 
}}
 
}}
 
Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):
 
Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):
  '''function''' <tex>\mathtt{binaryGcd(a, b)}:</tex>
+
  '''function''' binaryGcd(a, b) :
     '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{b}</tex> '''or''' <tex>\mathtt{b}</tex> == <tex>\mathtt{0}:</tex>
+
     '''if''' a == b '''or''' b == 0 :  
         '''return''' <tex>\mathtt{a}</tex>
+
         '''return''' a
     '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{0}:</tex>
+
     '''if''' a == 0 :  
         '''return''' <tex>\mathtt{b}</tex>
+
         '''return''' b  
     <font color=green>// первые два случая</font>
+
     <font color="darkgreen">// первые два случая</font>
     '''if''' <tex>\mathtt{a} \bmod 2 = 0:</tex>
+
     '''if''' a mod 2 = 0 :
         '''if''' <tex>\mathtt{b} \bmod 2 = 0:</tex>
+
         '''if''' b mod 2 = 0 :  
             '''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b\: /\: 2)} \cdot 2</tex>
+
             '''return''' binaryGcd(a / 2, b / 2) <tex>\cdot</tex> 2
 
         '''else'''
 
         '''else'''
             '''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b)}</tex>
+
             '''return''' binaryGcd(a / 2, b)
     <font color=green>// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font>
+
     <font color="darkgreen">// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font>
     '''if''' <tex>\mathtt{b} \bmod 2 = 0:</tex>
+
     '''if''' b mod 2 = 0 :  
         '''return''' <tex>\mathtt{binaryGcd(a, b\: /\: 2)}</tex>
+
         '''return''' binaryGcd(a, b / 2)
     <font color=green>// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex></font>
+
     <font color="darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex>
     <font color=green>// поэтому давайте всегда оставлять меньшее</font>
+
     // поэтому давайте всегда оставлять меньшее</font>
     '''if''' <tex>\mathtt{a} > \mathtt{b}:</tex>
+
     '''if''' a > b :  
         '''return''' <tex>\mathtt{binaryGcd((a - b)\: /\: 2, b)}</tex>
+
         '''return''' binaryGcd((a - b) / 2, b)
     '''return''' <tex>\mathtt{binaryGcd((b - a)\: /\: 2, a)}</tex>
+
     '''return''' binaryGcd((b - a) / 2, a)
  
 
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
 
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
  
Можно показать<ref>http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm</ref>, что этот алгоритм, в среднем на 60% более эффективен, чем классический. Но, к сожалению, в худшем случае он работает за <tex>O(\log^2\min(a, b))</tex>
+
Можно показать<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>ax + by = \gcd(a, b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: bx_1 + (a \bmod b)y_1 = \gcd(a, b)</tex>.
+
В стандартном алгоритме, мы использовали следующее свойство: <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 \frac{a}{b}\rfloor b</tex>. Получаем: <tex>bx_1 + (a \bmod b)y_1 = b x_1 + \left(a - \lfloor \frac{a}{b}\rfloor b\right)y_1 =  
+
Очевидно, что <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\left(x_1 - \lfloor \frac{a}{b}\rfloor y_1\right) + a y_1</tex>. Следовательно, приходим к расширенному алгоритму Евклида:
+
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>
 
  <font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font>
  '''function''' <tex>\mathtt{extendedGcd(a, b)}:</tex>
+
  '''function''' extendedGcd(a, b) :  
     '''if''' <tex>\mathtt{b} == 0:</tex>
+
     '''if''' b == 0 :  
         '''return''' <tex>\mathtt{a}, 0, 1</tex>
+
         '''return''' a, 1, 0
    <tex>\mathtt{gcd, x_1, y_1} \leftarrow \mathtt{extendedGcd(b, a} \bmod \mathtt{b)} </tex>
+
    gcd, <tex>x_1</tex>, <tex>y_1</tex> <tex>\leftarrow</tex> extendedGcd(b, a mod b)
    <tex>\mathtt{x} \leftarrow \mathtt{y_1}</tex>
+
    x <tex>\leftarrow</tex> <tex>y_1</tex>
     <tex>\mathtt{y} \leftarrow \mathtt{x_1} - (\mathtt{a} \text{ div } \mathtt{b}) \cdot \mathtt{y_1}</tex>
+
     y <tex>\leftarrow</tex> <tex>x_1</tex> - (a div b) <tex>\cdot</tex> <tex>y_1</tex>
     '''return''' <tex>\mathtt{gcd, x, y}</tex>
+
     '''return''' gcd, <tex>x</tex>, <tex>y</tex>
 
Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа <tex>x</tex> и <tex>y</tex> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
 
Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа <tex>x</tex> и <tex>y</tex> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
 +
 
== См. также==
 
== См. также==
 +
* [[Разложение_на_множители_(факторизация) | Разложение на множители]]
 +
* [[Простые_числа | Простые числа]]
 +
* [[Основная_теорема_арифметики | Основная теорема арифметики]]
  
 
== Примечания==
 
== Примечания==
 
<references />
 
<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]

Версия 21:12, 10 мая 2020

Определение:
Наибольшим общим делителем (англ. [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]коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

См. также

Примечания

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