Расширенный алгоритм Евклида — это алгоритм определения коэффициентов, позволяющих выразить наибольший общий делитель числовой пары через эти два числа.
Введение
Под алгоритмом Евклида понимается разработанный им алгоритм, позволяющий определить наибольший общий делитель целочисленной пары.
Древнегреческий математик Евклид жил в третьем веке до нашей эры. Он описал этот алгоритм в своей серии книг, называемых «Начала».
Данный алгоритм является старейшим числовым алгоритмом, который применяется и в настоящее время.
Для наипростейшего варианта применения алгоритма Евклида, берутся два целых положительных числа, и с помощью этого алгоритма находится ещё два числа, состоящие из числа меньшего веса и разности этих чисел. Эта операция циклически выполняется до тех пор, пока числа не сравняются. Полученное в итоге число и будет наибольшим общим делителем изначальной пары чисел. Евклид разработал алгоритм применительно лишь к натуральным числам и геометрическим понятиям, таким как длина, площадь, объём. Но в девятнадцатом веке нашей эры его обобщили и на другие математические понятия, например, целые Гауссовы числа и полиномы одной переменой. Дальнейшее развитие алгоритма вызвало внедрение термина евклидово кольцо. Затем алгоритм Евклида обобщили и на такие понятия математики как узлы и многомерные полиномы. Алгоритм нашёл много внедрений в области теории и практики. Например, на его базе создан криптографический алгоритм с открытым ключом RSA, который применяется в коммерческой сфере.
Расширенный алгоритм Евклида
Если стандартный алгоритм Евклида определяет наибольший общий делитель числовой пары $a$ и $b$, то расширенный алгоритм находит не только наименьший общий делитель, но и коэффициенты $x$ и $y$, для которых выполняется равенство:
$a • x + b • y = gcd (a, b)$.
То есть с его помощью определяются коэффициенты, при помощи которых наименьший общий делитель пары чисел можно выразить через саму пару этих чисел. Для определения этих коэффициентов необходимо получить формулы их изменения при переходе от пары $(a, b)$ к паре ($b$%$a, a$). Здесь символ процентов обозначает остаток от деления. Предположим, что существует решение ($X_1, Y_1$) для вновь созданной пары ($b$%$a, a$):
($b$%$a • X_1 + a • Y_1 = g$,
и надо найти решение ($x, y$) для искомой пары ($a, b$):
$a • x + b • y = g$.
Выполнив ряд преобразований, находим конечные формулы:
$x = y_1 – [b / a] • x_1$,
$y = x_1$.
