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

В то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел $a$ и $b$ , расширенный алгоритм Евклида находит помимо НОД также коэффициенты $x$ и $y$ такие, что:

$a \cdot x + b \cdot y = {\rm gcd} (a, b).$

Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Алгоритм

Внести вычисление этих коэффициентов в алгоритм Евклида несложно, достаточно вывести формулы, по которым они меняются при переходе от пары $(a,b)$ к паре $(b\%a,a)$ (знаком процента мы обозначаем взятие остатка от деления).

Итак, пусть мы нашли решение $(x_1,y_1)$ задачи для новой пары $(b\%a,a)$ :

$(b \% a) \cdot x_1 + a \cdot y_1 = g,$

и хотим получить решение $(x,y)$ для нашей пары $(a,b)$ :

$a \cdot x + b \cdot y = g.$

Для этого преобразуем величину $b \% a$ :

$b \% a = b - \left\lfloor \frac{b}{a} \right\rflo[...]$

Подставим это в приведённое выше выражение с $x_1$ и $y_1$ и получим:

$g = (b \% a) \cdot x_1 + a \cdot y_1 = \left( b -[...]$

и, выполняя перегруппировку слагаемых, получаем:

$g = b \cdot x_1 + a \cdot \left( y_1 - \left\lflo[...]$

Сравнивая это с исходным выражением над неизвестными $x$ и $y$ , получаем требуемые выражения:

$\cases{ x = y_1 - \left\lfloor \frac{b}{a} \righ[...]$

Реализация

 
int gcd (int a, int b, int & x, int & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	int x1, y1;
	int d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел $a$ и $b$ , но помимо этого — также искомые коэффициенты $x$ и $y$ в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай $a = 0$ . Тогда НОД равен $b$ , и, очевидно, требуемые коэффициенты $x$ и $y$ равны $0$ и $1$ соответственно. В остальных случаях работает обычное решение, а коэффициенты пересчитываются по вышеописанным формулам.

Расширенный алгоритм Евклида в такой реализации работает корректно даже для отрицательных чисел.

Литература

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ [2005]