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

Калькулятор, реализующий расширенный алгоритм Евклида.

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

ax + by = {\rm gcd} (a, b)

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

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

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

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

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

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

Пусть известны коэффициенты (x_1,y_1) для пары (b\%a,a), такие что:

 (b \% a)x_1 + ay_1 = g, и нужно рассчитать коэффициенты (x,y) для нашей пары (a,b), такие, что:

 ax + by = g

Раскроем выражение b\%a:

b\%a = b - \left\lfloor \frac{b}{a} \right\rfloor a, где

\left\lfloor \frac{b}{a} \right\rfloor — результат целочисленного деления b на a,

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

g = (b \% a) x_1 + a  y_1 = \left( b -\left\lfloor \frac{b}{a} \right\rfloor a\right) x_1 + ay_1

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

g = bx_1 + a \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1\right)

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

x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1
y = x_1

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

Ссылка скопирована в буфер обмена
PLANETCALC, Расширенный алгоритм Евклида

Комментарии