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

Для различных приложений очень важно уметь представлять наибольший общий делитель целых чисел а и b в виде (теорема 2.2.3). Очевидно, один из способов состоит в применении алгоритма Евклида и затем «обратного» прохода. Например, для получаем

откуда следует, что 18 — наибольший общий делитель чисел 612 и 342. Проведя вычисления в обратном порядке, получим

т.е. и мы решили нашу задачу.

Другой подход к решению этой задачи, имеющий, как мы убедимся в дальнейшем, много приложений, состоит в применении расширенного алгоритма Евклида. Значения вычисляются в серии шагов, в каждом из которых мы выражаем а, - (вычисленное в процессе работы алгоритма Евклида, разд. 2.2.2) в форме

А именно рассмотрим последовательность

В левом столбце — последовательность делений, которая нам уже встречалась раньше и которая теперь разрешена относительно остатков. В правом столбце каждый остаток выражен в виде мы хотим вычислить Очевидно, что Сравнивая обе части на шаге, имеем откуда получается следующая индуктивная процедура вычисления

Конечно, мы мажем также вычислить как но приведенное выше выражение подчеркивает, что вычислено таким же способом, как Мы получили следующий алгоритм.

ХБА. Расширенный алгоритм Евклида (Extended Euclidean Algorithm)

Вход:

Выход: такие, что

1. [Инициализация]

2. [Основной цикл] Пока выполнять

3. [Выход] Вернуть

Анализ времени работы аналогичен проведенному для ЕА, детали мы оставляем читателю. Применяя расширенный алгоритм Евклида в нашем примере получим:

Заметим, что равенство выполняется на каждом шаге. Алгоритм выдает проверим ответ: