Наибольший общий делитель — различия между версиями
Senya (обсуждение | вклад) (→Двоичный алгоритм Евклида) (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 5 участников) | |||
Строка 99: | Строка 99: | ||
Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последний ненулевой член этой последовательности. | Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последний ненулевой член этой последовательности. | ||
}} | }} | ||
− | '''Существование''' таких <tex>r_1, r_2, | + | '''Существование''' таких <tex>r_1, r_2, \cdots</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''. |
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений: | '''Корректность''' этого алгоритма вытекает из следующих двух утверждений: | ||
Строка 142: | Строка 142: | ||
|statement= | |statement= | ||
Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда | Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда | ||
− | * <tex>\gcd(2\ | + | * <tex>\gcd(2 \cdot a, 2 \cdot b) = 2 \cdot \gcd(a, b)</tex> |
− | * <tex>\gcd(2\ | + | * <tex>\gcd(2 \cdot a, 2 \cdot b + 1) = \gcd(a, 2 \cdot b + 1)</tex> |
− | * <tex>\gcd(2\ | + | * <tex>\gcd(2 \cdot a + 1, 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2 \cdot b + 1)</tex> |
|proof= | |proof= | ||
Тривиальным образом следует из определения | Тривиальным образом следует из определения | ||
Строка 174: | Строка 174: | ||
===Расширенный алгоритм Евклида=== | ===Расширенный алгоритм Евклида=== | ||
− | В стандартном алгоритме | + | В стандартном алгоритме мы использовали следующее свойство: <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 = | Очевидно, что <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</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''' extendedGcd(a, b) : | '''function''' extendedGcd(a, b) : | ||
'''if''' b == 0 : | '''if''' b == 0 : | ||
− | '''return''' a, 0 | + | '''return''' a, 1, 0 |
gcd, <tex>x_1</tex>, <tex>y_1</tex> <tex>\leftarrow</tex> extendedGcd(b, a mod b) | 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> | x <tex>\leftarrow</tex> <tex>y_1</tex> |
Текущая версия на 19:20, 4 сентября 2022
Определение: |
Наибольшим общим делителем (англ. | — greatest common divisor) для двух целых чисел и называется наибольшее натуральное , такое что делится на и делится на . Более формально,
Свойства НОД
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел
или не ноль.Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел:
Определение: |
Наибольший общий делитель для целочисленного множества | определяется как
Существует определение НОД через разложение числа на простые множители:
Утверждение: |
Пусть и — натуральные числа. Тогда где — делитель и . (Если не делится на будем считать, что присутствует в разложении в -ой степени.) |
Разложим основной теореме арифметики). Без ограничения общности, можно считать, что (если это не так, сделаем соответствующие и равными нулю). Очевидно, что в таком случае и на делятся на . Проверим его максимальность. Пусть существует , такое что и делятся на . Тогда оно необходимо будет раскладываться на те же простые множители, что и . Пусть и на множители: пусть , где — простые, а — натуральные (такие разложения существуют, по . Значит, существует . Из этого следует, что либо , либо . Но в первом случае, не окажется делителем , а во втором — . Значит, такого не существует. |
Связь с наименьшим общим кратным
Определение: |
Наименьшим общим кратным (англ. | — least common multiple) для двух чисел и называется наименьшее натуральное число, которое делится на и без остатка. Более формально
Существует представление НОК через разложение числа на простые множители:
Утверждение: |
Пусть и — натуральные числа. Тогда |
Доказательство полностью аналогично доказательству утверждения о НОД, с той лишь разницей, что мы заменяем на , а знаки неравенств — на противоположные. |
Наибольший общий делитель связан с наименьшим общим кратным следующим равенством:
Лемма: |
Пусть и — целые числа. Тогда . |
Доказательство: |
По утверждению о НОД и утверждению о НОК, пользуясь тем, что , получаем нашу лемму. |
Алгоритм Вычисления
Наивный алгоритм
В наивном методе, мы считаем, что нам известны разложения чисел
и на простые множители.//— множество простых чисел в разложении // — множество простых чисел в разложении // — степени простых чисел в разложении // — степени простых чисел в разложении function naiveGcd(p, q, , ): gcd 1 i, j 0, 0 while i < p.length() and j < q.length(): if == : t min( , ) gcd = gcd else if < : i += 1 else: j += 1 return gcd
Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов (
и ), только результат записывает не в массив, а агрегирует в переменной . Асимптотика равна минимуму из длин массивов и .Стандартный алгоритм Евклида
Теорема: |
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть |
Существование таких
, то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.Корректность этого алгоритма вытекает из следующих двух утверждений:
Лемма: |
Пусть , тогда |
Доказательство: |
|
Лемма: |
для любого ненулевого |
Далее, оценим асимптотику работы алгоритма.
Теорема: |
Алгоритм Евклида работает за |
Доказательство этого факта[1] достаточно громоздкое, поэтому не будем приводить его здесь.
Проще сформулировать алгоритм Евклида так: если даны натуральные числа
и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:
function euclideanGcd(a, b) : while b0 : t b b a mod b a t return a
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
Двоичный алгоритм Евклида
Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.
Для начала, опишем еще несколько свойств
:Утверждение: |
Пусть и — натуральные числа, тогда
|
Тривиальным образом следует из определения |
Пользуясь этим, и утверждением о НОДе нуля, определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):
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)2 else return binaryGcd(a / 2, b) // второй случай, только и поменяли местами if b mod 2 = 0 : return binaryGcd(a, b / 2) // остается третий случай. На самом деле, мы можем оставлять справа и , и // поэтому давайте всегда оставлять меньшее if a > b : return binaryGcd((a - b) / 2, b) return binaryGcd((b - a) / 2, a)
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений о НОДе четных и нечетных и о НОДе нуля).
Можно показать[2], что этот алгоритм, в среднем на 60% более эффективен, чем классический.
Расширенный алгоритм Евклида
В стандартном алгоритме мы использовали следующее свойство:
. Воспользуемся им для того, чтобы решить следующую задачу: найти и такие, что . Пусть мы нашли пару . Очевидно, что . Получаем: . Следовательно, приходим к расширенному алгоритму Евклида:// Алгоритм возвращает тройкуfunction extendedGcd(a, b) : if b == 0 : return a, 1, 0 gcd, , extendedGcd(b, a mod b) x y - (a div b) return gcd, ,
Такое представление наибольшего общего делителя называется соотношением Безу, а числа
и — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.См. также
Примечания
- ↑ Wolfram MathWorld — алгоритм Евклида
- ↑ http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm