homechevron_rightУчебаchevron_rightМатематика

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

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

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

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_1y = x_1

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

Комментарии