The extended Euclidean algorithm
Jason Holt
BYU Internet Security Research Lab
1 Oct 2002; revised October 2003
This document is in the public domain
----------------------------------------------

The simplest form of Euclid's algorithm finds the greatest common
divisor (gcd) of two numbers.

Simply stated, the gcd(x,y) with x>y is (recursively) equal to
gcd(y,x-y).  This works because the gcd divides both numbers evenly,
therefore the difference between them must also be divisible by the
gcd.

Likewise, a faster way to compute gcd(x,y) is to (recursively) find
gcd(y,x%y), since any multiples of y in x are multiples of the gcd,
and the remainder must also be a multiple of the gcd in order to reach
x.  Consider:

gcd(y, x) means: find maximal g such that y=ag and x=bg
x = ky+r for some k and r (namely, k=x/y and r=x%y).
Replacing for x and y:
bg = kag + r
r = bg-kag = (b-ka)g
So r must also be a multiple of g.
Therefore, with only a little hand-waving, gcd(y, x) = gcd(y, y%x).

This algorithm can also find values of a and b such that
ax+by=gcd(x,y).  This works because the steps of the gcd() algorithm
always deal with sums of multiples of x and y.  ax+by=gcd(x,y) turns
out to be useful when computing the multiplicative inverse of x modulo
y.

Consider an example:

gcd(120, 23)

120 / 23 = 5 r 5
23  / 5  = 4 r 3
5   / 3  = 1 r 2
3   / 2  = 1 r 1
2   / 1  = 2 r 0

In this case, the residue in the second-to-last line indicates that
the gcd is 1; that is, 120 and 23 are coprime.  Now do a little
algebra on each of the above lines:

120 / 23 = 5 r 5   =>  5 = 120 - 5*23
23  / 5  = 4 r 3   =>  3 = 23  - 4*5
5   / 3  = 1 r 2   =>  2 = 5   - 1*3
3   / 2  = 1 r 1   =>  1 = 3   - 1*2
2   / 1  = 2 r 0   =>  0 = 2   - 2*1

Now observe that the first line contains multiples of 120 and 23.
Also, the rightmost values are in each case the remainders listed on
the previous line, and the left side of the differences are the residues from
2 lines up.  We can thus progressively calculate each
successive remainder as sums of products of our two original values.

Here we rewrite the second equations in the above table:

  5 = 120 - 5*23  = 1*120            - 5*23
  3 = 23  - 4*5   = 1*23             - 4*(1*120  - 5*23)   =  -4*120 + 21*23
  2 = 5   - 1*3   = (1*120 - 5*23)   - 1*(-4*120 + 21*23)  =   5*120 - 26*23
  1 = 3   - 1*2   = (-4*120 + 21*23) - 1*(5*120  - 26*23)  =  -9*120 + 47*23

Notice that the last line says that 1 = -9*120 + 47*23, which is what
we wanted.

This means that 47 is the multiplicative inverse of 23 modulo 120.
Why? 23*23^-1 = 1 (mod 120) means that 23*23^-1 = 120k + 1, but that
means that 1 = 23*23^-1 - 120k.  47*23 - 9*120 = 1, so 47=23^-1.