Example

Use the following modified version of the Euclidean Algorithm to determine the greatest common divisor, $g$, of $22241739$ and $19848039$, as well as the solutions to $22241739x+19848039y=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 22241739 0 19848039 0 0 0
0 19848039 1 2393700 1 2393700 1
1 2393700 -8 698439 -8 698439 8
-8 698439 25 298383 25 298383 3
25 298383 -58 101673 -58 101673 2
-58 101673 141 95037 141 95037 2
141 95037 -199 6636 -199 6636 1
-199 6636 2927 2133 2927 2133 14
2927 2133 -8980 237 -8980 237 3
-8930 237 83747 0 83747 0 9

Appealing to the final pass above, and solving for $y$ in the original equation
$$22241739x+19848039y=237$$
then yields:

$$g=237 \quad , \quad x=-8980 \quad , \textrm{ and } y=10063$$