| Определение: |
| Наибольшим общим делителем (англ. [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] — целые числа из определения.
- Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а [math]r = a - bq = (t_1 - t_2 q)k [/math] (выражение в скобках есть целое число, следовательно, k делит r без остатка)
- Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
- Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
- В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
|
| [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]\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]O(\log^2\min(a, b))[/math]
Расширенный алгоритм Евклида
В стандартном алгоритме, мы использовали следующее свойство: [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] — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Примечания
