Linear Diophantine Equations - NUMBER THEORY - TWO PILLARS OF MATHEMATICS - Mathematics for the liberal arts

Mathematics for the liberal arts (2013)

Part II. TWO PILLARS OF MATHEMATICS

Chapter 5. NUMBER THEORY

5.10 Linear Diophantine Equations

We will again address the problem we introduced in the last section.

Problem: Let a, b, and c be integers, with a and b nonzero. Find all pairs of integers (x, y) such that ax + by = c.

When Are There Any Solutions?

Consider the Diophantine equation 2x + 6y = 17. Suppose that (x0, y0) is a solution. Then 2x0 is even (divisible by 2). But, since 6 is even, so is 6y0. Therefore, 2x0 + 6y0 is even. But 17 is odd, so 2x0 + 6y0 cannot equal 17. In other words, there are no solutions to 2x + 6y = 17. What makes this argument work? The fact that 2 | 2 and 2 | 16, but 2 images 17. This observation is the basis of the following theorem.

Theorem. The Diophantine equation ax + by = c has a solution if, and only if, gcd(a, b) divides c.

Proof. Let d = gcd(a, b), and (x0, y0) be a solution of ax + by = c. Since d | a and d | b, we have d | ax0 and d | by0. Hence d | (ax0 + by0), so d | c. This gives us half of the theorem (only if).

Now suppose that d | c, say c = de. We need to show that ax + by = c has a solution. We can use Bézout’s Identity, which tells us that there are integers u and v such that au + bv = d. Multiply by e:

images

So

images

Thus (ue, ve) is a solution of the equation.

images

images EXAMPLE 5.23

Which of the following Diophantine equations are solvable?

(a) 14x + 35y = 119

(b) 24x – 32y = 106

(c) 7x – 17y = 10004

Solution: (a) You can verify that gcd(14,35) = 7, and 71119 (since 119 = 7 · 17), so 14x + 35y = 119 is solvable.

(b) The gcd of 24 and –32 is 8, but 8 images 106, so 24x – 32y = 106 is not solvable.

(c) The gcd of 7 and – 17 is 1, which divides 10004 since it divides everything. So 7x – 17y = 10004 has solutions.

images

We now know exactly which linear Diophantine equations have solutions. Next, we will see what the sets of solutions look like.

Complete Sets of Solutions

Let us look a bit closer at the first equation in the last example: 14x + 35y = 119. We saw that 14, 35, and 119 are all divisible by 7, so let’s divide the whole equation by 7, to get 2x + 5y = 17. From elementary algebra, we know that the solutions of this new equation are exactly the same as the solutions to the old one. (If this doesn’t sound familiar, take a moment to convince yourself—it isn’t hard.) But the new equation is simpler. You can easily solve it. Try!

In general, suppose that ax + by = c is a solvable Diophantine equation, i.e., that gcd(a, b) divides c. If gcd(a, b) > 1, we can divide ax + by = c by gcd(a, b) to get a new equation a′x + b′y = c′, which has the same solutions as the original one. The new equation is, however, simpler. In particular, a′ and b′ are relatively prime, since we have divided out the common factors.

So we have reduced the problem of finding solutions of linear Diophantine equations to that of finding solutions to equations where gcd(a, b) = 1. The following theorem addresses that important case.

Theorem. Let gcd(a, b) = 1 and (x0, y0) be a solution of ax + by = c. Then every solution is of the form (x0 + bt, y0at) for some integer t.

Proof. Let (r, s) be a solution of our equation. We need to show that there is some integer t such that r = x0 + bt and s = y0at. Let t = (y0s)/a. This gives us s = y0at. We need to show that t is an integer, and that r = x0 + bt.

First we show that t is an integer, in other words, that a divides y0s. Because (x0, y0) and (r, s) are solutions, we know the following.

(5.1) images

(5.2) images

Subtracting equation (5.2) from equation (5.1) yields

images

Rearranging terms,

(5.3) images

Now a | a(x0r) and a | 0, so a | b(y0s). We can apply a result from Section 5.6: since a divides the product b(y0s), and gcd(a, b) = 1, it follows that a divides y0s. This is what we needed for t to be an integer.

Finally, we show that r = x0 + bt. From the definition of t, we have y0s = at. Substituting at into equation (5.3) for y0s gives

images

Since a ≠ 0, we can divide this equation to get x0r + bt = 0, which yields r = x0 + bt. images

Putting this theorem together with the one from the last section gives us a satisfying result.

Theorem. Let gcd(a, b) = 1 and (x0, y0) be any solution of the Diophantine equation ax + by = c. Then a pair of integers is a solution if, and only if, it is of the form (x0 + bt, y0at) for some integer t.

images EXAMPLE 5.24

Find all solutions of the Diophantine equation 22x + 143y = – 66.

Solution: First we note that gcd(22, 143) = 11. So divide the equation by 11 to get the equivalent 2x + 13y = –6. One solution of this is (–3, 0), so the solutions are pairs of the form (– 3 + 13t, 0 – 2t), or (–3 + 13t, –2t).

It is always a good idea to check your answer. In this case it is easy; substitute x = –3 + 13t and y = – 2t into the original equation.

images

Computing Solutions

In the last section, we saw how to find entire solution sets to an equation, provided we had the first solution. How do we find that first solution? If the equation is simple, it may be easiest to eyeball a solution. For harder equations, or if we want to tell computers how to find solutions, we need a more organized way. There is a way, using Bézout’s Identity.

We start with the theorem that we mentioned earlier: The equation ax + by = c has a solution if, and only if, gcd(a, b) divides c. Suppose that we have such an equation, and let us call gcd(a, b) = d. Then d divides c, say c = ed.Now we know from Bézout that we can find integers u and v such that au + bv = d. Then

images

In other words, (eu, ev) is a solution to our equation!

How to solve the linear Diophantine equation ax + by = c.

i. Run the Euclidean Algorithm to find gcd(a, b), say d.

ii. Find the pair (u, v) of Bézout’s Identity.

iii. Multiply (u, v) by c/d to get a single solution of the original equation.

iv. Divide the equation by d to get an equivalent equation (one with the same solutions), ax + by = c′, with gcd (a′, b′) = 1.

v. Use the solution of (iii) and the last theorem to get the entire solution set.

images EXAMPLE 5.25

Solve 145x + 160y = 35.

Solution: (i) First we run the Euclidean Algorithm to find gcd(145, 160).

images

So gcd(145, 160) = 5.

(ii) Next, we compute the integers u and v of Bézout’s Identity. Proceeding as in Section 5.6, we express each of the remainders ri above in the form ri = 145xi + 160yi. First, express 15 that way,

images

then 10,

images

and finally 5:

images

Thus u = –11 and v = 10 work.

(iii) Since 35 = 7 · 5, we can multiply (u, v) by 7 to get our solution. In other words, multiply (– 11, 10) by 7, to get (– 77, 70). As always, we check our answer:

images

(iv) Divide our equation by 5 (the gcd) to get 29x + 32y = 7.

(v) Finally, using the solution in (iii) and the equation in (iv), our entire set of solutions is

images

EXERCISES

5.57 Find all solutions to the following Diophantine equations.

a) 3x + 4y = 5

b) 3x – 4y = 5

c) 10x + 22y = 15

d) 209x + 143y = 176

e) 209x + 143y = 99

5.58 Cuthbert purchased a number of bottles of soft drinks, namely, Passionate Peach at $2.40 per bottle, and Marvelous Mango at $2.10 a bottle. He spent $46.50 all together. How much of each type could he have bought?

5.59 A simplified version of American football allows teams to score 7 points on a touchdown, or 3 points on a field goal. What scores are possible?