extended euclidian algorithm

Extended euclidian algorithm

$a,b\in \mathbb{Z},0<b<a$

$$\begin{array}{r}\gcd (a,b)=1\\ ⟹\exists x,y:ax+by=1\end{array}$$

Steps:

$a$	$b$	$q$	$r$	EA $\downarrow$	$x$	$y$	EEA $\uparrow$
$a_0=a$	$b_0=b$	$\lfloor \frac{a_0}{b_0}\rfloor$	$r_0=a_0\mathrm{mod}{b}_0$	Start	$x_0=y_1$	$y_0=x_1-q_0\cdot y_1$	Stop
$a_1=b_0$	$b_1=r_0$	$\lfloor \frac{a_1}{b_1}\rfloor$	$r_1=a_1\mathrm{mod}{b}_1$		$x_1=y_2$	$y_1=x_2-q_1\cdot y_2$
$⋮$	$⋮$	$⋮$	$⋮$		$⋮$	$⋮$
$a_t=b_{t-1}$	$b_t=r_{t-1}$	$\lfloor \frac{a_t}{b_t}\rfloor$	$r_t=a_t\mathrm{mod}{b}_t$	$r_t=\gcd (a,b)$	$x_t=y_{t+1}$	$y_t=x_{t+1}-q_t\cdot y_{t+1}$	Check: $1=a_t{x}_t+b_t{y}_t$
$a_{t+1}=b_t$	$b_{t+1}=r_t$	$\lfloor \frac{a_{t+1}}{b_{t+1}}\rfloor$	$r_{t+1}=0$	$r_{t+1}=0$ $⟹$Stop	$x_{t+1}=0$	$y_{t+1}=1$	Start

$\gcd (23,17)$

$a$	$b$	$q$	$r$	EA $\downarrow$	$x$	$y$	EEA $\uparrow$; Check
$23$	$17$	$1$	$6$		$3$	$-4$	$23(3)+17(-4)=69-68=1$
$17$	$6$	$2$	$5$		$-1$	$3$	$17(-1)+6(3)=-17+18=1$
$6$	$5$	$1$	$1$		$1$	$-1$	$6(1)+5(-1)=6-5=1$
$5$	$1$	$5$	$0$		$0$	$1$	$5(0)+1(1)=0+1=1$