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

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

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

Калькулятор ниже, а описание алгоритма, как водится, под ним.

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

Первое число

Второе число

Рассчитать

НОД

 

Коэффициент перед большим числом

 

Коэффициент перед меньшим числом

 

 Ссылка  Сохранить  Виджет

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

Пусть известны коэффициенты для пары , такие что:

, и нужно рассчитать коэффициенты для нашей пары , такие, что:

Раскроем выражение :

, где

— результат целочисленного деления b на a,

и подставим в выражение:

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

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

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