Rasshirenny_algoritm_Evklida

Расширенный алгоритм Евклида — это расширение алгоритма Евклида, которое вычисляет кроме наибольшего общего делителя (НОД) целых чисел a и b ещё и коэффициенты соотношения, то есть целые x и y.
Коэффициенты соотношения — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами.

x0 = 1 ; y0 = 0
X1 = 0 ; y1 = 1
Для вычисления дополнительных коэффициентов:
X = X(i-2) – (q * X(i-1));
Y = Y(i-2) – (q * Y(i-1));
НОД(a, b) = a * x + b * y
Изначально мы решаем как и по обычному методу:
НОД(a, b) = (a = b * q + r)

x0 = 1 ; y0 = 0
X1 = 0 ; y1 = 1
X = X(i-2) – (q * X(i-1));
Y = Y(i-2) – (q * Y(i-1));
Допустим:
a = 64; b = 42
64 = 42 * 1 + 22;
42 = 22 * 1 + 20;
22 = 20 * 1 + 2
20 = 2 * 10 + 0
НОД(64 и 42) = 2
X2 = 1 – (1 * 0) = 1
X3 = 0 – (1 * 1) = -1
X4 = 1 – (1 * (-1)) = 2
Y2 = 0 – (1 * 1) = -1
Y3 = 1 – (1 * (-1)) = 2
Y4 = (-1) – (1 * 2) = - 3
НОД(a, b) = (a * x) + (b * y) =
= 64 * 2 + 42 * (-3) = 128 + (-126) = 2