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

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

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

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

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

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

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

Rearranging,

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

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