Алгоритм Евклида

Алгоритм Евклида находит наибольший общий делитель двух чисел (НОД, greatest common divisor) без разложения на множители. Две версии: через вычитание — $O(\max (a,b))$, через остаток — $O(\log \max (a,b))$.

Зачем нужно

Определение. $\text{НОД}(a,b)=k$, если $k$ — максимальное число, для которого $a⋮k$ и $b⋮k$.

НОД можно найти через разложения: $24=2\cdot 2\cdot 2\cdot 3$, $30=2\cdot 3\cdot 5$, общая часть $2\cdot 3=6$. Но разложение само по себе стоит $O(N)$ на каждое число — см. разложение на простые множители в АиСД L02. Евклид обходится без него.

Как работает

Свойства

1. $\text{НОД}(a,b)=\text{НОД}(b,a)$;
2. $\text{НОД}(a,b)=\text{НОД}(a,b-a)$, если $b\ge a$;
3. $\text{НОД}(a,1)=1$, $\text{НОД}(a,0)=a$;
4. $\text{НОД}(a,b)=\text{НОД}(a,b\%a)$, если $b\ge a$.

Свойства 2 и 4 — всё, на чём стоит алгоритм: пара заменяется меньшей парой с тем же НОД, пока одно из чисел не станет нулём, а $\text{НОД}(a,0)=a$.

Не из лекции: доказательство свойства 2

На лекции записаны два определения — $k$ для пары $(a,b)$ и $k_2$ для $(a,b-a)$ — и связь $(b-a)⋮k_2\iff b⋮k_2$. Целиком:

У пар $(a,b)$ и $(a,b-a)$ одни и те же общие делители.

• Если $a=tx$ и $b=ty$, то $b-a=t(y-x)$ — $t$ делит $b-a$.
• Если $a=tx$ и $b-a=tz$, то $b=t(z+x)$ — $t$ делит $b$.

Множества общих делителей равны, значит, равны и их максимумы. ∎

Не из лекции: доказательство свойства 4

$b\%a=b-qa$, где $q$ — неполное частное. Свойство 2, применённое $q$ раз подряд, даёт $\text{НОД}(a,b)=\text{НОД}(a,b-qa)$. ∎

Свойство 3: у единицы единственный делитель 1; на $a$ делятся и $a$, и $0=a\cdot 0$, а больше $a$ делителя у $a$ нет.

Версия 1: вычитание

пока a ≠ 0 и b ≠ 0
    если a > b
        a = a - b
    иначе
        b = b - a
вывести(a + b)

$T(a,b)=O(a+b)=O(\max (a,b))$.

Пример — 11 шагов: $(124,24)\to (100,24)\to (76,24)\to (52,24)\to (28,24)\to (4,24)\to (4,20)\to (4,16)\to (4,12)\to (4,8)\to (4,4)\to (0,4)$, ответ 4.

Версия 2: остаток

Серия вычитаний одного числа — это остаток от деления (Целочисленное деление и остаток): от $(124,24)$ до $(4,24)$ пять раз вычиталось 24, и $4=124\%24$.

пока a ≠ 0 и b ≠ 0
    если a > b
        a = a % b
    иначе
        b = b % a
вывести(a + b)

$T(a,b)=O(\log \max (a,b))$ — на лекции без доказательства. На том же примере — два шага: $(124,24)\to (4,24)\to (4,0)$.

Не из лекции: почему выводится $a+b$

Цикл кончается, когда одно число — ноль. Тогда $a+b$ — второе число, а по свойству 3 оно и есть НОД. Все шаги сохраняли НОД (свойства 2 и 4), значит, это НОД исходной пары.

Не из лекции: доказательство оценок

Вычитание. Пока оба числа положительны, каждый шаг уменьшает $a+b$ хотя бы на 1. Шагов не больше $a+b$, а $\max (a,b)\le a+b\le 2\max (a,b)$ — оценки $O(a+b)$ и $O(\max (a,b))$ совпадают. Оценка точная: пара $(N,1)$ требует $N-1$ шагов.

Остаток. Лемма: при $b\ge a>0$ верно $b\%a<b/2$.

• $a\le b/2$: $b\%a<a\le b/2$;
• $a>b/2$: частное равно 1, $b\%a=b-a<b/2$.

Каждый шаг заменяет большее число остатком, то есть уменьшает его больше чем вдвое. После этого большим становится другое число, и следующий шаг уменьшает уже его. За каждые два шага $\max (a,b)$ падает хотя бы вдвое, поэтому шагов не больше $2{\log }_2\max (a,b)+2$. Это $O(\log \max (a,b))$ — см. Асимптотические оценки.

Тонкости

• На доске оценка записана как $O(\log (\max (a+b)))$ — видимо, описка вместо $\max (a,b)$. Разница асимптотически не важна: $\log (a+b)\le 1+{\log }_2\max (a,b)$.

Не из лекции: крайние случаи

• В обеих версиях $a,b\in \mathbb{N}$. При $a=b=0$ цикл не выполнится ни разу и выведет 0, хотя $\text{НОД}(0,0)$ определением с лекции не задан: на 0 делится всё, максимума нет.
• Разница версий заметна на неравных числах: $(10^9,1)$ — почти миллиард шагов вычитанием и один шаг с остатком.

Частые ошибки

• Использовать версию с вычитанием там, где числа могут сильно различаться.
• Путать остаток % с частным /: a = a / b не сохраняет НОД.