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

Алгоритм Евклида можно записать несколько иначе:

$r_i = r_{i-2} - k_i·r_{i-1}$,

где $k_i$ - результат целочисленного деления $r_{i-2}$ на $r_{i-1}$

$r_2 = a \pmod b = a - k_2·b$

$r_3 = b \pmod {r_2} = b - k_3·r_2 = b - k_3·(a - k_2 \cdot b) = a \cdot (-k_3) + b \cdot(1 + k_2 * k_3)$

$r_4 = ...$

При такой записи видно, что каждый остаток представляет собой линейное уравнение вида:

$r_i = a·s_i + b·t_i$, где $s_i$, $t_i$ - целые

$gcd(a,b) = a·s_{n-1} + b·t_{n-1}$

$gcd(a,b) = a·s + b·t$, где $s$, $t$ - целые

Последнее выражение называется соотношение Безу

Нам известны $r_0 = a, r_1 = b, a > b$

$s_0 = 1, t_0 = 0$

$s_1 = 0$, $t_1 = 1$

Выразим $s_i$, $t_i$ через их предыдущие значения

$r_i = r_{i-2} - k_i·r_{i-1}$,

$a·s_i + b·t_i = (a·s_{i-2} + b·t_{i-2}) - k_i·(a·s_{i-1} + b·t_{i-1})$,

$a·s_i + b·t_i = (a·s_{i-2} + b·t_{i-2}) - (k_i·a·s_{i-1} + k_i·b·t_{i-1})$,

$a·s_i + b·t_i = a·(s_{i-2} - k_i·s_{i-1}) + b·(t_{i-2} - k_i·t_{i-1})$,

$s_i = s_{i-2} - k_i·s_{i-1}$,

$t_i = t_{i-2} - k_i·t_{i-1}$,

В отличие от простого алгоритма Евклида, в расширенном алгоритме важен порядок $a$, $b$, т.к. коэффициент $s$ соответствует первому аргументу, а коэффициент $t$ соответствует второму аргументу