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)\). 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 \]

Since \(d\) is the greatest common divisor, \(b/d\) does not divide \(a\). But it must divide the right-hand side (since \(b\) appears there) so \((x'-x)\) is some multiple of \(b/d\), 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 💡