Prove $s_{i-1}t_i-t_{i-1}s_i=(-1)^i$ in the extended Euclidean algorithm.

31 Views Asked by At

We apply extended Euclidean algorithm for $$s_ia+t_ib=r_i$$ to find $\gcd(a,b)$ ($b>a$). The initial value is, $t_{-1}=1, t_0=0, s_{-1}=1,s_0=0$.

So, $s_{-1}t_{0}-t_{-1}s_{0}=(-1)^i$. Accroding to Wikipedia, $$s_{i-1}t_i-t_{i-1}s_i=(-1)^i$$ will be satisfied. How to prove this?

1

There are 1 best solutions below

2
On BEST ANSWER

If $a=bq+r$, then $$ \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} b \\ r \end{bmatrix}$$ The matrix has determinant $-1$ and so does its inverse.

All steps in the extended Euclidean algorithm are like that.