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? 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.
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 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 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:
Thus \(\gcd(33, 27) = \gcd(27, 6)\). Repeating this trick:
and we see \(\gcd(27, 6) = \gcd(6,3)\). Lastly,
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 > 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
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 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
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
Let \(d = \gcd(a,b)\), and let \(b = b'd, a = a'd\). 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
Rearranging,
Dividing by \(d\) gives:
The numbers \(a'\) and \(b'\) are coprime since \(d\) is the greatest common divisor, hence \((x'-x)\) is some multiple of \(b'\), 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 wish to solve \(1 = x p + y q\) for coprime integers \(p\) and \(q\). In this case, the above becomes