Given three integers $a,b,c$, can you write $c$ in the form

$$c=ax+by$$

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 just $(a,b)$ if no confusion is caused. 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.

Euclid's algorithm (also known as the Euclidean algorithm) finds $(a,b)$ by repeatedly doing something that most people learn in primary school: division and remainder. We give an example of how it works, and leave the proof of the general case to the reader.

Suppose we wish to compute $\gcd (\mathrm{27,33})$. Then first we divide the bigger one by the smaller one:

$$33=1\times 27+6$$

Suppose an integer $d$ divides the left-hand side. In other words, suppose $d\mid 33$. Suppose in addition $d\mid 27$. Then in order for $d$ to divide the right-hand side we require $d\mid 6$. Hence any common divisor of $33$ and $27$, including the greatest one, is a divisor of $6$. Moreover, every integer that divides 6 and also divides 27 clearly must divide 33. Thus $\gcd (33,27)=\gcd (27,6)$, and we have reduced the original problem to a smaller problem. We proceed in the same way; division and remainder:

$$27=4\times 6+3$$

and by the same argument $\gcd (27,6)=\gcd (\mathrm{6,3})$. Lastly

$$6=2\times 3+0$$

So since 6 is a perfect multiple of 3, $\gcd (\mathrm{6,3})=3$, and we have found that $\gcd (\mathrm{33,27})=3$.

This algorithm does not involve factorizing numbers. It is quite fast. We obtain a crude bound for the number of steps required by observing that if we divide $a$ by $b$ to get $a=bq+r$, and $r>b/2$, then in the next step we get a remainder $r\prime \le b/2$. Thus every two steps, the numbers shrink by at least one bit.

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=ma+nb$$

using the extended Euclidean algorithm.

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=xa+yb.$$

Let $d=\gcd (a,b)$. Now $xa+yb$ 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=kd$. Using the extended Euclidean algorithm we can find $m,n$ such that $d=ma+nb$, thus we have a solution $x=km,y=kn$.

Suppose $x\prime ,y\prime$ is another solution. Then

$$c=xa+yb=x\prime a+y\prime b$$

Rearranging,

$$(x\prime -x)a=(y-y\prime )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\prime -x)$ is some multiple of $b/d$, that is

$$x\prime -x=tb/d$$

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

$$y\prime -y=ta/d$$

Thus $x\prime =x+tb/d$ and $y\prime =y-ta/d$ for some integer $t$.

But if we replace $t$ with any integer, $x\prime$ and $y\prime$ still satisfy $c=x\prime a+y\prime b$. Thus there are infinitely many solutions, and they are given by

$$x=km+tb/d,y=kn+ta/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=xp+yq$. Then the above becomes

$$x=m+tq,y=n+tp.$$