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$? If so, is there more than one solution, and what are they? Before answering this, let us answer a seemingly unrelated question:

How do you find the greatest common divisor (gcd) of two given 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 it is not known how we can do this efficiently.

Amazingly, a few simple observations lead to a far superior method: Euclid’s algorithm (also known as 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 to a smaller size: we just need to find $\gcd(a, a - b)$. We can repeat this and eventually 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)$. Then 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 give us more information than just 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 this procedure, until we have used all the equations and found $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, n$ such that

\[ c = x a + y b . \]

Let $d = \gcd(a,b)$. Now $x a + y b$ is a multiple of $d$ for any integers $x, y$, thus if $c$ is not a multiple of $d$ then there are no solutions.

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 be given this case: coprime integers $p$ and $q$ are given, and we wish to solve $1 = x p + y q$. Then the above becomes

\[ x = m + t q, y = n + t p . \]