Language In this article a,b,c,…, 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/_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 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×3³ and b = 2³×3²×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 ax+by=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 ax+by=c, where a and b have no common factors. Consider the equation 7x+11y=100 (which was given in the September 1999 Six problems), 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×8)+(11×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 …, −2,−1,0,1,2,… of k, we obtain an infinite set of solutions, namely

k	x	y
...	...	...
-2	-14	18
-1	-3	11
-1	-3	11
0	8	4
1	19	-3
2	30	-10
...	...	...

which can be written in the form (x,y) as

…,  (−14,18),  (−3,11),  (8,4),  (19,−3),  (30,−10),… .

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 ax+by=c. Suppose that x=x₀ and y=y₀ is a solution of this equation. Then, for every whole number k,

a(x0+bk)+b(y0−ak) = (ax0+by0) +abk−abk = c,

so that x₀+bk and y₀−ak is also a solution. This shows that all of the following are solutions to ax+by=c:

k		x	y
...		...	...
-2		x0 −2b	y0 +2a
-1		x0−b	y0+a
0		x0	y0
1		x0+b	y0−a
2		x0+2b	y0−2a
...		...	...

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₁ and y=y₁. Then

ax1 +by1 = c = ax0 +by0,

so that

a(x1−x0)=b(y0−y1).

As a and b have no common factors, we see that b must divide x₁−x₀. This means that there is some whole number k such that x₁−x₀ = bk, and so x₁ = x₀+bk. As this gives

b(y0−y1) = a(x1−x0) = a(x0 +bk−x0) = abk,

we find that y₁ = y₀−ak, Thus the solution we started with, namely x=x₁ and y=y₁ is x=x₀+bk, y₁=y₀−ak, and this is one of the solutions in the list above. We have now shown that all solutions of ax+by=c, where a and b have no common factors, are in the list above, and therefore the general formula for the solution is x=x₀ +bk and y=y₀−ak for any whole number k. With this formula, once you have found one solution (x₀ and y₀) you have found them all !

The previous article in the series was Euclid's Algorithm I.