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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Стандартный алгоритм Евклида)
(Двоичный алгоритм Евклида)
Строка 131: Строка 131:
 
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
 
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
 
===Двоичный алгоритм Евклида===
 
===Двоичный алгоритм Евклида===
 +
Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.
 +
 +
Для начала, опишем еще несколько свойств <tex>gcd</tex>:
 +
{{Утверждение
 +
|statement=
 +
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа, тогда
 +
* <tex>\gcd(2a, 2b) = 2\cdot\gcd(a, b)</tex>
 +
* <tex>\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)</tex>
 +
|proof=
 +
Тривиальным образом следует из определения
 +
}}
  
 
===Расширенный алгоритм Евклида===
 
===Расширенный алгоритм Евклида===

Версия 02:55, 31 января 2017

Определение:
Наибольшим общим делителем (англ. [math]\gcd[/math]greatest common divisor) для двух целых чисел [math]m[/math] и [math]n[/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]\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 [math]\mathtt{naiveGcd}(p, q, \alpha, \beta):[/math]
    [math]\mathtt{gcd} \leftarrow 1[/math]
    [math]\mathtt{i, j} \leftarrow 0, 0[/math]
    while [math]\mathtt{i} \lt  p\mathtt{.length()}[/math] and [math]\mathtt{j} \lt  q\mathtt{.length()}:[/math]
        if [math]p_i[/math] == [math] q_j:[/math]
            [math]\mathtt{t} \leftarrow \min(\alpha_i, \beta_j)[/math]
            [math]\mathtt{gcd} = \mathtt{gcd} \cdot p_i^{\mathtt{t}}[/math]
        else if [math]p_i \lt  q_j:[/math]
            [math]\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1[/math]
        else:
            [math]\mathtt{j} \mathrel{+}\mathrel{\mkern-2mu}= 1[/math]
    return [math]\mathtt{gcd}[/math]

Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов ([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 [math]\mathtt{euclideanGcd}(\mathtt{a, b}):[/math]
    while [math]\mathtt{b} \neq 0:[/math]
        [math]\mathtt{t} \leftarrow \mathtt{b}[/math]
        [math]\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}[/math]
        [math]\mathtt{a} \leftarrow \mathtt{t}[/math]
    return [math]\mathtt{a}[/math]

Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. 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]\triangleright[/math]
Тривиальным образом следует из определения
[math]\triangleleft[/math]

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

Формулы для [math]r_i[/math] могут быть переписаны следующим образом:

[math]r_1 = a + b(-q_0)[/math]
[math]r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)[/math]
[math]\cdots[/math]
[math]\gcd (a,b) = r_n = as + bt[/math]

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и tкоэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Связь с цепными дробями

Отношение [math]a/b[/math] допускает представление в виде цепной дроби:

[math]\frac ab=[q_0; q_1, q_2,\cdots,q_n][/math].

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу [math]t/s[/math], взятому со знаком минус:

[math][q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts[/math].

Примечания