## Introduction

The statement of the Extended Euclidean Algorithm Theorem. (Extended Euclidean Algorithm.) Let `m`

and `n`

be positive integers. Define:

a[0] = m, a[1] = n,
q[k] = Floor (a[k-1]/a[k]) for k > 0,
a[k] = a[k-2] - a[k-1] q[k-1] for k > 1,
x[0] = 1, x[1] = 0, y[0] = 0, y[1] = 1,
x[k] = x[k-2] - q[k-1] x[k-1] for k > 1,
y[k] = y[k-2] - q[k-1] y[k-1] for k > 1.

If `a[p]`

is the last nonzero `a[k]`

, then:

a[p] = (m,n) = x[p] m + y[p] n.

(The `Floor`

of a real number `x`

is the greatest integer less than or equal to `x`

. So `Floor(1.5)`

= 1, `Floor(-2.1)`

= -3, and `Floor(0)`

= 0.)

Don't be alarmed by all the subscripts! Believe it or not, the algorithm isn't bad for hand computation if you're careful to arrange the numbers in a table.

Before I give the proof, here's a quick overview. The `q`

s compute the greatest common divisor by successive division, i.e., using the standard Euclidean algorithm. Nothing new there! The `x`

s and `y`

s are for bookkeeping; they eventually yield the coefficients in the linear combination.

Proof. I'll take for granted the statement and proof of the standard Euclidean algorithm.

Ignoring the `x`

s and `y`

s, the computation of the `a`

s and `q`

s is the same as the computation of the standard Euclidean algorithm: the `a`

s are the remainders, and the `q`

s are the quotients. Thus, the algorithm terminates, and when it does, the last nonzero `a`

is the greatest common divisor `(m,n)`

.

I claim that:

x[k]a[0] + y[k]a[1] = a[k] for k > 0.

I'll prove this using induction.

For `k`

= 1, I have:

x[1]a[0] + y[1]a[1] = 0[1] a[0] + 1[1] a[1] = a[1].

Now, take `k`

> 1, and assume that the result is true for all indices less than or equal to `k`

. I want to prove the result for `k`

+ 1. Compute:

x[k+1] a[0] + y[k+1] a[1] =
(x[k-1] - q[k] x[k]) a[0] + (y[k-1] - q[k] y[k]) a[1] =
(x[k-1] a[0] + y[k-1] a[1]) - q[k] (x[k] a[0] + y[k] a[1]) =
a[k-1] - q[k] a[k] =
a[k+1].

The first equality comes from the definition of the `x`

s and the `y`

s. I used the induction hypothesis to get the third equality. The last equality uses the definition of the `a`

s.

The result is true for `k`

+ 1, so it's true for all `k`

> 0, by induction. In particular, if `a[p]`

= `(m,n)`

is the last nonzero `a`

, then:

x[p] a[0] + y[p] a[1] = a[p] = (m,n).

## The Extended Euclidean Algorithm

If `m`

and `n`

are integers (not both 0), the greatest common divisor `(m,n)`

of `m`

and `n`

is the largest integer which divides both `m`

and `n`

. The Euclidean algorithm uses repeated division to compute the greatest common divisor.

The greatest common divisor of `m`

and `n`

can be expressed as an integer linear combination of `m`

and `n`

. That is, there are integers `c`

and `d`

such that,

(m,n) = c m + d n.

There are infinitely many pairs of numbers `c`

, `d`

that work; sometimes, you can find a pair by trial and error. For example, (10,7) = 1, and by juggling numbers in my head, I see that:

1 = (-2)(10) + (3)(7).

On the other hand, (367,221) = 1, but it's not likely that you'd figure out that:

1 = (-56)(367) + (93)(221)

by juggling numbers in your head!

The Extended Euclidean Algorithm computes the greatest common divisor `(m,n)`

of integers `m`

and `n`

, as well as numbers `c`

and `d`

such that:

(m,n) = c m + d n.