§ Теоретическое обоснование

Сегодня я попытаюсь разобрать алгоритм Евклида в его расширенном варианте. Что это значит? Что значит "расширенный"? Это просто. Вот мы нашли НОД(a,b)=d, но нам надо узнать вот что:
То есть, нам надо найти такой x и такой y, при умножении на которое у нас получится d (см. формулу выше). Вот пример. Найдем НОД(3,12) и он равен 3, потому что как 12, так и 3 делятся на 3. Хорошо, мы его нашли, выпишем:
Где a=3, b=12, d=НОД(3,12). И как теперь узнать, какие будут x, y? Автор классной книги, его звать Кнут (и пряник, ага), нашел этот отличный метод и назвал его "Расширенный алгоритм Евклида". Начнем по-порядку. Сначала надо вспомнить то выражение, которое мы разбирали в прошлой статье про алгоритм Евклида:
Где НОД(a,b) = НОД(b,r). Это было доказано ранее. Теперь посмотрим, как происходит обычно поиск НОД по этому алгоритму. Как мы помним, чтобы перейти к следущей итерации, надо разделить "a" на "b", получить q, и остаток, и применить их как новые "a" и "b".

Шаг	Поиск НОД	Разложение остатков	Описание
1			, теперь они вместо
2			, теперь они вместо
3			, теперь они вместо
4			, теперь они вместо
....
			, теперь они вместо
			Точка остановки

Все, что происходит тут - это просто магия. Обычная магия, которая происходит в фентези. Ложим в пробирку немного математических ингредиентов и начинаем смешивать. Немного выстоять... и зелье готово! Теперь немного придется включить воображение и приглядеться к формулам. Мы заметили, что:
И еще то, что:
И поэтому:
Давайте теперь подставим в формулу выше формулу ту, что ниже:
Раскроем скобки и перегруппируем:
Теперь приглядимся внимательно... так вот что мы видим? Мы видим, что коэффициентами перед a и b у нас стоят
и :
Да это просто шикарно! То есть, чтобы вычислить следующий и , нужно всего лишь знать предыдущие 2! Вот в этом и есть сила расширенного алгоритма Евклида.
Тут встает вопрос. Вот мы хотим вычислить и , то есть, нам нужны коэффициенты (, , ), и где их достать? А тут все просто. Взглянем на таблицу. У нас , то если мы попробуем найти , то в таком случае , и , судя по таблице.
Это значит, что:
Отсюда:
Вот такой вот он, расширенный алгоритм Евклида. И результатом НОД будет .

§ Программная реализация

А теперь время программного обеспечения.

1// Расширенный НОД
2int extnod(int a, int b, int* x, int* y) {
3
4    int q, r;
5    int x2 = 1, y2 = 0, // x(i-2)=1, y(i-2)=0
6        x1 = 0, y1 = 1; // x(i-1)=0, y(i-1)=1
7
8    do {
9
10        // Алгоритм Евклида
11        q = a / b;
12        r = a % b;
13        a = b;
14        b = r;
15
16        // Расширенный алгоритм Евклида
17        *x = x2 - x1*q; // x(i) = x(i-2) - x(i-1)*q
18        *y = y2 - y1*q; // y(i) = y(i-2) - y(i-1)*q
19
20        // "Сдвиг истории" назад
21        x2 = x1; y2 = y1; // Старый x(i-1), y(i-1) перемещается в x(i-2), y(i-2)
22        x1 = *x; y1 = *y; // Новый  x(i), y(i) становится x(i-1), y(i-1)
23
24    } while (r > 0); // Перебирать, пока не станет r = 0
25
26    // И записать разультат, где x = x(i-1), y = y(i-1)
27    // т.к. ранее мы "сдвинули" в (x2, y2) старые (x1, y1)
28    *x = x2; *y = y2;
29
30    // Вернуть значение НОД
31    return a;
32}