## 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 .$