# Euclid's Algorithm

Given three integers \(a, b, c\), can you write \(c\) in the form

for integers \(x\) and \(y\)? If so, is there 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.

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 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 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:

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

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

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 > 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

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

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

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

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

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

Rearranging,

Dividing by \(d\) gives:

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

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

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

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

*blynn@cs.stanford.edu*💡