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

Мы будем говорить, что последовательность \(a\), содержащая хотя бы два элемента, построена при помощи алгоритма Евклида тогда и только тогда, когда \(a_{n+2}\equiv a_{n}\) по модулю \(a_{n+1}\) для любого допустимого \(n\).

Например, следующие последовательности построены при помощи алгоритма Евклида:

• 3, 42
• 3, 42, 3
• 3, 42, 45, -3, 0
• 8, 5, 3, 2, 1, 0, 1, 5, 6

Фундаментальное свойство алгоритма Евклида

Если последовательность \(a\) построена при помощи алгоритма Евклида, то множество общих делителей \(a_{n}\) и \(a_{n+1}\) совпадает с множеством общих делителей \(a_{n+1}\) и \(a_{n+2}\).

Это напрямую следует из (тривиально проверяемого) свойства: если \(d\) является делителем \(a\) и \(n\), причём \(a\equiv_{n} b\), то \(d\) является делителем \(b\).

Алгоритм Евклида для нахождения НОД

Поскольку наибольший общий делитель \(x\) и нуля равен абсолютной величине \(x\), то если алгоритм Евклида дал последовательность, содержащую ноль, по соседством с ним в этой последовательности стоит (с точностью до знака) НОД начальной пары чисел.

Обеспечить наличие нуля в такой последовательности весьма просто:

def gcd(a, b):
    while b != 0: a, b = b, a%b
    return abs(b)

Говоря русским языком, достаточно в качестве очередного элемента последовательности брать остаток от деления предпредыдущего элемента на предыдущий.

Вообще говоря, для каждой пары \(a\) и \(b\), в которой \(a\) не делится на \(b\), существует ровно два числа \(x\), для которых выполнено одновременно

• \(|x| < |b|\)
• \(a\equiv_{b} x\)

Эти числа: остаток \(r\) от деления \(a\) на \(b\) и \(r-|b|\).

Более того, среди этих двух чисел хотя бы одно по абсолютной величине не превышает половину \(b\).

Поэтому правильный выбор следующего числа позволяет получить ноль за количество шагов, не превышающее логарифм второго из начальной пары элементов последовательности.

Более того, даже если выбирать следующее число как просто остаток (например, подобно вышеприведённой программе), асимптотическая сложность алгоритма останется той же: если \(r > |b|/2\), то \(|b|-r\) является остатком от деления \(b\) на \(r\). Поэтому мы при выборе «неправильного» числа потратим всего лишь один лишний шаг на каждый такой «неправильный» выбор.

Переопределение

Договоримся далее под алгоритмом Евклида понимать именно такой, который порождает последовательность, заканчивающуюся нулём.

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

Рассмотрим уравнение в целых числах (отностельно неизвестных \(x\) и \(y\))

\[ ax + by = c \]

Заметим сперва, что если НОД \(a\) и \(b\) не делит \(c\), то решений, очевидно, нет. А если делит, то на него можно сократить обе части.

Поэтому без ограничения общности считаем, что \(a\) и \(b\) взаимно просты (то есть их НОД равен 1).

Решить уравение \(ax+by=c\) — в точности то же самое, что найти все \(x\), удовлетворяющие сравнению

\[ ax \equiv_b c \]

Если к этому сравнению приписать всегда верное

\[ bx \equiv_b 0 \]

то к полученной паре сравнений можно применить алгоритм Евклида (сравнения можно складывать и вычитать, а, соответственно, и говорить о сравнимости (в аспекте делимости нацело) сравнений по модулю сравнения), приводящий к

\[ \pm\text{НОД}(a,b)x \equiv_b \ldots \]

Учитывая взаминою простоту \(a\) и \(b\), получаем необходимое условие на \(x\) вида «\(x\) сравним с чем-то».

Оказывается, это условие является ещё и достаточным: у уравнения \(ax + by = c\) обязано быть хотя бы одно решение.

Это доказывается тоже при помощи алгоритма Евклида, который нужно применить к равенствам

\[ \begin{aligned} a\cdot 1 + b\cdot 0 & = a \\ a\cdot 0 + b\cdot 1 & = b \end{aligned} \]

получив равенство вида

\[ a\cdot A + b\cdot B = \pm1 \]

которое затем остаётся умножить на \(c\) или \(-c\) в зависимости от знака правой части.

Итого

Мы доказали следующее:

• у уравнения \(ax + by = c\)
• и, что эквивалентно, у сравнения \(ax\equiv_b c\)

есть решение тогда и только тогда, когда \(c\) делится на НОД \(a\) и \(b\), причём это решение (в аспекте неизвестного \(x\)) единственно по модулю частного \(b\) и упомянутого НОД.

Если записывать единственность в аспекте обоих неизвестных, то решение имеет вид

\[ \begin{aligned} x & = A + (b/d)\cdot k \\ y & = B - (a/d)\cdot k \end{aligned} \]

где \(d\) — НОД \(a\) и \(b\), а \(k\) — произвольное целое число.