# Euclid's Algorithm

Given three integers $$a, b, c$$, can you write $$c$$ in the form

$c = a x + b y$

for integers $$x$$ and $$y$$? Can there be more than one solution? Can you find them all? Before answering this, let us answer a seemingly unrelated question:

How do you find the greatest common divisor (gcd) of two integers $$a, b$$?

We denote the greatest common divisor of $$a$$ and $$b$$ by $$\gcd(a,b)$$, or sometimes even just $$(a,b)$$. If $$(a,b) = 1$$ we say $$a$$ and $$b$$ are coprime.

The obvious answer is to list all the divisors $$a$$ and $$b$$, and look for the greatest one they have in common. However, this requires $$a$$ and $$b$$ to be factorized, and no one knows how to do this efficiently.

Amazingly, a few simple observations lead to a far superior method: Euclid’s algorithm, or the Euclidean algorithm. First, if $$d$$ divides $$a$$ and $$d$$ divides $$b$$, then $$d$$ divides their sum. Similarly, $$d$$ must also divide their difference, $$a$$ - $$b$$, where $$a$$ is the larger of the two. But this means we’ve shrunk the original problem: now we just need to find $$\gcd(a, a - b)$$. We can repeat until we reach a trivial case.

Hence we can find $$\gcd(a,b)$$ by doing something that most people learn in primary school: division and remainder. We give an example and leave the proof of the general case to the reader.

Suppose we wish to compute $$\gcd(27,33)$$. First, we divide the bigger one by the smaller one:

$33 = 1 \times 27 + 6$

Thus $$\gcd(33, 27) = \gcd(27, 6)$$. Repeating this trick:

$27 = 4 \times 6 + 3$

and we see $$\gcd(27, 6) = \gcd(6,3)$$. Lastly,

$6 = 2 \times 3 + 0$

So since 6 is a perfect multiple of 3, $$\gcd(6,3) = 3$$, and we have found that $$\gcd(33,27) = 3$$.

This algorithm does not require factorizing numbers, and is fast. We obtain a crude bound for the number of steps required by observing that if we divide $$a$$ by $$b$$ to get $$a = b q + r$$, and $$r \gt b / 2$$, then in the next step we get a remainder $$r' \le b / 2$$. Thus every two steps, the numbers shrink by at least one bit.

## Extended Euclidean Algorithm

The above equations actually reveal more than the gcd of two numbers. We can use them to find integers $$m,n$$ such that

$3 = 33m + 27n$

First rearrange all the equations so that the remainders are the subjects:

$6 = 33 - 1 \times 27$
$3 = 27 - 4\times 6$

Then we start from the last equation, and substitute the next equation into it:

$3 = 27 - 4\times(33 - 1\times 27) = (-4)\times 33 + 5\times 27)$

And we are done: $$m = -4, n = 5$$.

If there were more equations, we would repeat until we have used them all to find $$m$$ and $$n$$.

Thus in general, given integers $$a$$ and $$b$$, let $$d = \gcd(a,b)$$. Then we can find integer $$m$$ and $$n$$ such that

$d = m a + n b$

using the extended Euclidean algorithm.

## The General Solution

We can now answer the question posed at the start of this page, that is, given integers $$a, b, c$$ find all integers $$x, y$$ such that

$c = x a + y b .$

Let $$d = \gcd(a,b)$$, and let $$b = b'd, a = a'd$$. Since $$x a + y b$$ is a multiple of $$d$$ for any integers $$x, y$$, solutions exist only when $$d$$ divides $$c$$.

So say $$c = k d$$. Using the extended Euclidean algorithm we can find $$m, n$$ such that $$d = m a + n b$$, thus we have a solution $$x = k m, y = k n$$.

Suppose $$x' ,y'$$ is another solution. Then

$c = x a + y b = x' a + y' b$

Rearranging,

$(x' - x)a = (y - y')b$

Dividing by $$d$$ gives:

$(x' - x)a' = (y - y')b'$

The numbers $$a'$$ and $$b'$$ are coprime since $$d$$ is the greatest common divisor, hence $$(x'-x)$$ is some multiple of $$b'$$, that is:

$x'-x = t b / d$

for some integer $$t$$. Then solving for $$(y - y')$$ gives

$y'-y = t a / d$

Thus $$x' = x + t b /d$$ and $$y' = y - t a / d$$ for some integer $$t$$.

But if we replace $$t$$ with any integer, $$x'$$ and $$y'$$ still satisfy $$c = x' a + y' b$$. Thus there are infinitely many solutions, and they are given by

$x = k m + t b / d , y = k n + t a /d .$

for all integers $$t$$.

Later, we shall often wish to solve $$1 = x p + y q$$ for coprime integers $$p$$ and $$q$$. In this case, the above becomes

$x = m + t q, y = n + t p .$

Ben Lynn blynn@cs.stanford.edu 💡