Наибольший общий делитель

Если даны два числа целых числа $a$, $b$, то $g = gcd(a, b)$ это наибольшее число, что $a \vdots g$ и $b \vdots g$

Примечание. gcd - greatest common divider

Теорема

Для целых неотрицательных чисел $a$, $b$, таких что $a \geq b$, верно

\[gcd(a, b) = gcd(a - b, b)\\gcd(a, b) = gcd(a ~\%~ b, b)\]

Доказательство

Пусть $gcd(a, b) = g$.

Тогда $a \vdots g$ и $b \vdots g$, значит, $a - b \vdots g$.

Очевидно, что у $a - b$ и $b$ нет общих делителей, больших $g$, значит

\[gcd(a - b, b) = gcd(a, b) = g\]

Покажем, что из этого следует и $gcd(a, b) = gcd(b, a ~\%~ b)$.

Мы знаем, что

\[gcd(a, b) = gcd(b, a - b)\]

Тогда, если $b > a - b$, то $a - b = a ~\%~ b$.

Иначе мы можем, используя то же утверждение, показать, что

\[gcd(b, a - b) = gcd(b, a - 2b) \\ gcd(b, a - 2b) = gcd(b, a - 3b) \\ \dots \\ gcd(b, a - (k - 1)b) = gcd(b, a - kb)\]

Таким образом, повторяя этот переход, мы подберём такое наибольшее целое k, что

\[b > a - kb \\ a ~\%~ b = a - kb\]

Альтернативное доказательство (сразу с остатком)

Возьмём какое-то натуральное число $k$, такое, что и $a$, и $b$ делятся на $k$, то есть

\[a = t_1 k, ~ t_1 \in \mathbb{N}_0 \\ b = t_2 k, ~ t_2 \in \mathbb{N}_0\]

Поделим $a$ на $b$ с остатком, то есть подберём числа $q$ и $r$ такие, что

\[a = bq + r ~~~ q, r \in \mathbb{N}_0 \\ 0 \le r < b\]

Если $a = bq + r$, то

\[t_1 k = t_2 k q + r \Leftrightarrow r = k(t_1 - t_2 q)\]

Тогда $t_1 - t_2 q$ целое, а значит, $r \vdots k$.

Аналогично можно доказать, что если $b$ и $r$ делятся на какое-то число, то и $a$ делится на него.

Тогда $gcd(a, b) = gcd(b, r) = gcd(b, a ~\%~ b)$.

Алгоритм

Заметим, что $\forall a: gcd(a, 0) = a$.

Реализуем алгоритм Евклида в виде рекурсивной функции gcd(a, b).

\[gcd(a, b) = \begin{cases} gcd(b, a ~\%~ b) & a \ge b \gt 0 \\ a & b = 0 \end{cases}\]

Ясно, что $b > a ~\%~ b$, то есть $b$ каждый раз уменьшается и достигнет 0, завершив алгоритм.

Асимптотика

Заметим, что для всяких $a$ и $b$ $a ~\%~ b < \frac{a}{2}$.

И правда: если $a = bk + r$, где $r \geq \frac{a}{2}$, то $b \leq bk \leq \frac{a}{2} \leq r \Rightarrow b \leq a ~\%~ b$, что невозможно по определению остатка.

Рассмотрим какие-нибудь числа $a$ и $b$, на которых запустим наш алгоритм Евклида. Посмотрим на первые два шага работы алгоритма (допустим, он работал хотя бы два шага):

\[(a, b) \rightarrow (b, a ~\%~ b) \rightarrow (a ~\%~ b, b ~\%~ (a ~\%~ b))\]

Используя вышесказанное утверждение, можно показать, что

\[a ~\%~ b < \frac{a}{2} \\ b ~\%~ (a ~\%~ b) < \frac{b}{2} \\ a ~\%~ b + b ~\%~ (a ~\%~ b) < \frac{a + b}{2}\]

Видно, что после двух шагов сумма чисел уменьшается вдвое.

Это значит, что за $2 log_2 (a + b)$ шагов алгоритм точно сойдётся.

Таким образом мы получаем довольно грубую оценку асимптотики $O(log(a + b))$.