Example

Use the following modified version of the Euclidean Algorithm to determine the greatest common divisor, $g$, of $31875$ and $8387$, as well as the solutions to $31875x+8387y=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 31875 0 8387 0 0 0
0 8387 1 6714 1 6714 3
1 6714 -1 1673 -1 1673 1
-1 1673 5 22 5 22 4
5 22 -381 1 -381 1 76
-381 1 8387 0 8387 0 22

Appealing to the final pass above, and solving for $y$ in the original equation ($31875x+8387y=1$) then yields:

$$g=1 \quad , \quad x=-381 \quad , \textrm{ and } y=1448$$