Euclid's Algorithm II
Introduction We continue the discussion given in Euclid's Algorithm I, and here we shall discover when an equation of the form $a x+b y=c$ has no solutions, and when it has infinitely many solutions. We shall also discover how to write down a formula which gives all of these solutions. We begin by explaining some
mathematical language.
Language In this article $a,b,c,\ldots, x,y,z$ are all whole numbers (but they can be positive, negative or zero). To say that a number $d$ divides $a$ means that ${a\over d}$ is a whole number or, equivalently, that $a$ is a multiple of $d$. Another way of saying this is to say that $d$ is a divisor of $a$. As an example, 9 is a divisor of 54 (because ${54\over 9}=6$) but 7 is not a divisor of 54. The number $d$ is a common divisor of $a$ and $b$ if $d$ is a divisor of both $a$ and $b$; for example, 6 is a common divisor of 54 and 360 (54 and 360 are both in the 6 times table). Among all of the common divisors of
$a$ and $b$ there is a largest, and this is called the greatest common divisor of $a$ and $b$. For example, if $a=54$ and $b=360$ then $a=2\times 3^3$ and $b= 2^3\times 3^2\times 5$, so that the common divisors of $a$ and $b$ are 1, 2, 3, 6, 9 and 18. The greatest common divisor of 54 and 360 is 18. Notice that each common divisor of $a$ and $b$ divides
the greatest common divisor of $a$ and $b$. This general fact can most easily be seen by writing $a$ and $b$ as products of prime factors.
No solutions Consider the equation $2x+4y=13$ (which we discussed in the first article). This has no solutions because $2x+4y$ must be even and 13 is odd. Similarly, the equation $3x+27y=17$ has no solutions because the left hand side is a multiple of 3 while the right hand side is not. So, in general, the equation $ax+by=c$ has no solutions if there
is a number $d$ which divides $a$ and $b$ but not $c$. In other words, if the greatest common divisor of $a$ and $b$ does not divide $c$, then the equation $ax+by=c$ has no solutions . For example, the greatest common divisor of 3 and 27 is 3, and as this does not divide 17 the equation $3x+27y=17$ has no solutions.
Infinitely many solutions - a typical example We now consider those equations $a x+b y=c$ which do have solutions, and we shall show that in this case there are infinitely many solutions. Because this equation has a solution, the greatest common divisor, say $d$, of $a$ and $b$ divides $c$, so we can divide both sides of the equation by $d$. After we
have done this we are left with an equation of the form $a x+b y=c$, where $a$ and $b$ have no common factors. Consider the equation $7x+11y=100$ (see the problem In Particular ), and note that 7 and 11 have no common factors. It is easy to see that one solution of this equation is $x=8$ and $y=4$, and we shall now show that by adding any multiple of 11 to $x$,
and subtracting the same multiple of 7 from y we get another solution. So consider $x=8+11k$ and $y=4-7k$. As
$$ 7(8+11k)+11(4-7k)= (7\times 8)+(11\times 4) +77k -77k = 100,$$ we see that for every $k$, we get a solution $x=8+11k$ and $y=4-7k$. Thus if we take the values $\ldots, -2,-1,0,1,2,\ldots $ of $k$, we obtain an infinite set of solutions, namely
| $k$ | $x$ | $y$ |
|---|---|---|
| $\ldots$ | $\ldots$ | $\ldots$ |
| -2 | -14 | 18 |
| -1 | -3 | 11 |
| -1 | -3 | 11 |
| 0 | 8 | 4 |
| 1 | 19 | -3 |
| 2 | 30 | -10 |
| $\ldots$ | $\ldots$ | $\ldots$ |
which can be written in the form $(x,y)$ as $$\ldots, \ (-14,18), \ (-3,11), \ (8,4), \ (19,-3), \ (30,-10),\ldots\ .$$
The next section gives a general formula, but you may prefer to use this section as a model for other examples (for instance, $4x+5y=9$).
Infinitely many solutions - the general case We can follow the same argument for a general equation $a x+b y=c$. Suppose that $x=x_0$ and $y=y_0$ is a solution of this equation. Then, for every whole number $k$,
$$a(x_0+b k)+b(y_0-a k) = (a x_0+b y_0) +a b k-a b k = c,$$
so that $x_0+b k$ and $y_0-a k$ is also a solution. This shows that all of the following are solutions to $a x+b y=c$:
| $k$ | $x$ | $y$ | |
|---|---|---|---|
| $\ldots$ | $\ldots$ | $\ldots$ | |
| -2 | $x_0 -2b$ | $y_0 +2a$ | |
| -1 | $x_0-b$ | $y_0+a$ | |
| 0 | $x_0$ | $y_0$ | |
| 1 | $x_0+b$ | $y_0-a$ | |
| 2 | $x_0+2b$ | $y_0-2a$ | |
| $\ldots$ | $\ldots$ | $\ldots$ |
Could there be any other solutions other than those we have just listed? We shall now show that there are not. To do this let us consider any solution whatever, say $x=x_1$ and $y=y_1$. Then
$$a x_1 +b y_1 = c = a x_0 +b y_0,$$
so that
$$a(x_1-x_0)=b(y_0-y_1).$$
As $a$ and $b$ have no common factors, we see that $b$ must divide $x_1-x_0$. This means that there is some whole number $k$ such that $x_1-x_0 = b k$, and so $x_1 = x_0+b k$. As this gives
$$b(y_0-y_1) = a(x_1-x_0) = a(x_0 +b k-x_0) = a b k,$$
we find that $y_1 = y_0-a k$, Thus the solution we started with, namely $x=x_1$ and $y=y_1$ is $x=x_0+b k$, $y_1=y_0-a k$, and this is one of the solutions in the list above. We have now shown that all solutions of $a x+b y=c$, where $a$ and $b$ have no common factors, are in the list above, and therefore {\it the general formula for the solution is $x=x_0 +b k$ and $y=y_0-a k$ for any whole number $k$}. With this formula, once you have found one solution ($x_0$ and $y_0$) you have found them all!
For previous article in series, click here . See also the next article Approximations, Euclid's Algorithm and Continued Fractions to find out how Euclid's algorithm can be used for any numbers, not just integers, and how it is used to find rational approximations very quickly, such as approximations to pi.