Example

Use the following modified version of the Euclidean Algorithm to determine the greatest common divisor, $g$, of $19789$ and $23548$, as well as the solutions to $19789x+23548y=g$

  1. Set $x=1$, $g=a$, $v=0$, $w=b$, $s=0$, and $t=0$.
  2. If $w=0$, let $y=(g-ax)/b$ and stop.
  3. Find $q$ and $t$ so that $g = qw + t$, with $0 \le t \lt w$.
  4. Set $s=x-qv$
  5. Set $(x,g) = (v,w)$
  6. Set $(v,w) = (s,t)$
  7. Go to step ii.

The values of the variables after each pass through the algorithm is given in the table below:

$x$ $g$ $v$ $w$ $s$ $t$ $q$
1 19789 0 23548 0 0 0
0 23548 1 19789 1 19789 0
1 19789 -1 3759 -1 3759 1
-1 3759 6 994 6 994 5
6 994 -19 777 -19 777 3
-19 777 25 217 25 217 1
25 217 -94 126 -94 126 3
-94 126 119 91 119 91 1
119 91 -213 35 -213 35 1
-213 35 545 21 545 21 2
545 21 -758 14 -758 14 1
-758 14 1303 7 1303 7 1
1303 7 -3364 0 -3364 0 2

Appealing to the final pass above, and solving for $y$ in the original equation ($19789x+23548y=7$) then yields:

$$g=7 \quad , \quad x=1303 \quad , \textrm{ and } y=-1095$$