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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Наивный алгоритм)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(→‎Стандартный алгоритм Евклида)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 125: Строка 125:
  
 
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
 
Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
−
  '''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.
  

Версия 00:08, 11 мая 2018

Определение:
Наибольшим общим делителем (англ. [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 = bq_0 + r_1[/math]
[math]b = r_1q_1 + r_2[/math]
[math]r_1 = r_2q_2 + r_3[/math]
[math]\cdots[/math]
[math]r_{k-2} = r_{k-1} q_{k-1} + r_k[/math]
[math]\cdots[/math]
[math]r_{n-1} = r_n q_n[/math]
Тогда [math]\gcd(a, b) = r_n[/math] — последний ненулевой член этой последовательности.

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

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

Лемма:
Пусть [math]a = bq + r[/math], тогда [math]\gcd (a,b) = \gcd (b,r).[/math]
Доказательство:
[math]\triangleright[/math]

Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда [math] a = t_1 k [/math] ; [math] b = t_2 k; [/math] где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.

  1. Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а [math]r = a - bq = (t_1 - t_2 q)k [/math] (выражение в скобках есть целое число, следовательно, k делит r без остатка)
  2. Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
  3. Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
  4. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
[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(2a, 2b) = 2\cdot\gcd(a, b)[/math]
  • [math]\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)[/math]
  • [math]\gcd(2a + 1, 2b + 1) = \gcd(\left|a - b\right|, 2b + 1)[/math]
[math]\triangleright[/math]
Тривиальным образом следует из определения
[math]\triangleleft[/math]

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

function [math]\mathtt{binaryGcd(a, b)}:[/math]
    if [math]\mathtt{a}[/math] == [math]\mathtt{b}[/math] or [math]\mathtt{b}[/math] == [math]\mathtt{0}:[/math]
        return [math]\mathtt{a}[/math]
    if [math]\mathtt{a}[/math] == [math]\mathtt{0}:[/math]
        return [math]\mathtt{b}[/math]
    // первые два случая
    if [math]\mathtt{a} \bmod 2 = 0:[/math]
        if [math]\mathtt{b} \bmod 2 = 0:[/math]
            return [math]\mathtt{binaryGcd(a\: /\: 2, b\: /\: 2)} \cdot 2[/math]
        else
            return [math]\mathtt{binaryGcd(a\: /\: 2, b)}[/math]
    // второй случай, только [math]a[/math] и [math]b[/math] поменяли местами
    if [math]\mathtt{b} \bmod 2 = 0:[/math]
        return [math]\mathtt{binaryGcd(a, b\: /\: 2)}[/math]
    // остается третий случай. На самом деле, мы можем оставлять справа и [math]a[/math], и [math]b[/math]
    // поэтому давайте всегда оставлять меньшее
    if [math]\mathtt{a} \gt  \mathtt{b}:[/math]
        return [math]\mathtt{binaryGcd((a - b)\: /\: 2, b)}[/math]
    return [math]\mathtt{binaryGcd((b - a)\: /\: 2, a)}[/math]

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

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

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

В стандартном алгоритме, мы использовали следующее свойство: [math]\gcd(a, b) = \gcd(b, a \bmod b)[/math]. Воспользуемся им для того, чтобы решить следующую задачу: найти [math]x[/math] и [math]y[/math] такие, что [math]ax + by = \gcd(a, b)[/math]. Пусть мы нашли пару [math]x_1, y_1: \: bx_1 + (a \bmod b)y_1 = \gcd(a, b)[/math]. Очевидно, что [math]a \bmod b = a - \lfloor \frac{a}{b}\rfloor b[/math]. Получаем: [math]bx_1 + (a \bmod b)y_1 = b x_1 + \left(a - \lfloor \frac{a}{b}\rfloor b\right)y_1 = b\left(x_1 - \lfloor \frac{a}{b}\rfloor y_1\right) + a y_1[/math]. Следовательно, приходим к расширенному алгоритму Евклида: 

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

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

См. также

Примечания

  1. ↑ Wolfram MathWorld — алгоритм Евклида
  2. ↑ http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Наибольший_общий_делитель&oldid=65317»