Bezout's identity: general solutions???

Question

S O L V E D

After using the Euclidean algorithm to find the greatest common divisor between $ a = r_{-1} $ and $ b = r_0 $ (see figure) I'm trying to express in a general way the solution (x and y) of the correlated Bezout's identity.

In figure I have indicated the solutions where the Euclidean algorithm has 1, 2, 3, 4, 5 and 6 steps.

I would like a solution for the case where the Euclidean algorithm has n steps.

For the $n^{th}$-case, using "continuants", we have: $y= (-1)^{n-1} K_{n-1}(q_1 , q_2 , ... q_{n-1})$ where $K_0=1 ; K_1=q_1$.

$x= (-1)^{n} K_{n-1}(q_1 , q_2 , ... q_{n-1})$ where $K_0=0 ; K_1=1$.

Answer 1

What you are looking for is continuants. The Wikipedia article Continued fraction mentions continuants in context. The Wikipedia article Continuants states

The $n$-th continuant $\,K_n(x_1,x_2,\dots,x_n)\,$ is defined recursively by $$ K_0 = 1; \\ K_1(x_1) = x_1; \\ K_n(x_1,x_2,\dots,x_n) = x_nK_{n-1}(x_1,x_2,\dots,x_{n-1}) + K_{n-1}(x_1,x_2,\dots,x_{n-2}).$$

The recursion explains why the number of terms are Fibonacci numbers.