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.9 Diophantine Equations

Definitions and Examples

An enclosure at the zoo holds ostriches and opossums. Between them, they have 30 eyes and 44 feet. How many of each type of animal is there?

At two eyes per animal, we have a total of 30/2 = 15 animals. If all the possums were to lift two feet off the ground, so that every animal would have two feet on the ground, we would have 2 · 15 = 30 feet left on the ground. So 44 – 30 = 14 feet were lifted. At 2 feet per opossum, there must be 14/2 = 7 opossums. That leaves 15 – 7 = 8 ostriches.

We can also solve this problem by writing down and solving equations. Let x be the number of ostriches and y the number of opossums. That there are 44 feet can then be written 2x + 4y = 44. Let us make the problem harder here, and forget that there are 30 eyes, and just consider this equation. What are the possible solutions? In fact, there are an infinite number of solutions. For any number x, we have a solution where y = (44 – 2x)/4.

But if we think about the origin of this equation, many of the above solutions don’t work. We can’t, for example, have x = 21 and y = 1/2, without being cruel to an opossum. Letting x = – 2 and y = 12 doesn’t work either. We must, under the circumstances, insist that both x and y be nonnegative integers. You can check that, with this restriction, there are exactly twelve solutions.

In this section and the next, we will consider equations whose solutions are restricted in a particular way. A Diophantine equation is an equation whose solutions are required to be integers. They are named in honor of the Greek mathematician Diophantus, who lived in Alexandria in the 3rd century CE.

We are already familiar with some types of Diophantine equations. Bézout’s Identity concerns the Diophantine equation ax + by = gcd(a, b). Another famous Diophantine equation comes from the Pythagorean Theorem: x2 + y2 = z2. For example, one solution is x = 3, y = 4, z = 5, since 32 + 42 = 52. This type of Diophantine equation had already been studied by the time of Euclid.

We will now consider the simplest type of Diophantine equation with two variables: linear equations.

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.

Some Geometry

Let us consider the Diophantine equation 2x + 3y = 17. If we forget for a moment that our solutions must be integers, we can think of this as a regular equation and graph it. It is a line (Figure 5.3).

Figure 5.3 The graph of 2x + 3y = 17.

images

What is the graph of this equation? It is the set of ordered pairs (x, y) such that 2x + 3y = 17. So the solution to our problem consists of points on this line, but not just any points, since x and y have to be integers. If we mark all points (x, y) where both x and y are integers, the picture looks like Figure 5.4.

Figure 5.4 The graph of 2x + 3y = 17 and the integer lattice.

images

The set of integer points in the plane is called the integer lattice. Solving our Diophantine equation means finding all the points that are on both the line and the integer lattice.

Now let’s go back to the line, and put a point (x0, y0) on it (Figure 5.5).

Suppose that (x0, y0) is a solution to our Diophantine equation. The geometry of the line suggests another solution. Recall that the slope of the line 2x + 3y = 17 can be obtained by putting the equation into slope-intercept form: y = (–2/3)x + 17/3, so the slope is –2/3. This means that, if we start from a point on the line, go 3 units to the right, and down 2, we get another point on the line (Figure 5.6).

Figure 5.5 The graph of 2x + 3y = 17 with one solution.

images

Figure 5.6 The graph of 2x + 3y = 17 with two solutions.

images

To check this, you can plug (x0 + 3, y0 – 2) into the equation and see that it works. And of course both x0 + 3 and y0 – 2 are also integers, so are solutions also of our Diophantine equation. In the same way, we can find more solutions (Figure 5.7).

Figure 5.7 The graph of 2x + 3y = 17 with multiple solutions.

images

We summarize this in the following theorem.

Theorem. Let (x0, y0) be a solution to the Diophantine equation ax + by = c, and t be any integer. Then (x0 + bt, y0at) is also a solution.

Proof. We are given that ax0 + by0 = c. Using this,

images

so (x0 + bt, y0at) solves the equation. It is easy to see that x0 + bt and y0at are integers, so the theorem is proven.

images

images EXAMPLE 5.22

Find four solutions to 5x + 6y = 17.

Solution: By trial and error, we find that (x, y) = (1, 2) works. Letting t = –1 , 1 , 2, we get three more solutions.

If t = – 1, then we get the solution (– 5, 7).

If t = 1, then we get the solution (7, – 3).

If t = 2, then we get the solution (13, – 8).

EXERCISES

5.53 Find the 12 solutions to 2x + 4y = 44, where x and y are nonnegative integers.

5.54 For each of the following Diophantine equations, find, if possible, three solutions.

a) 4x + 6y = 26

b) 2x + 4y = 3

c) 6x – 3y = 15

5.55 Alice bought a number of $3 pens and $7 notebooks. If she spent $37 altogether, what are the possibilities for the numbers of pens and notebooks?

5.56 A certain forest is made up of trees planted in a square pattern, with one foot between adjacent pairs of trees. A marksman is challenged to stand by one of the trees and shoot his rifle in such a way so as to miss every tree. It takes an exact aim to hit a tree. (The trees are very thin. In fact, the thickness of each trunk is so small that it can’t be measured.)

The marksman, who is also a mathematician, thinks to himself: “Let this tree I’m standing by be the origin of a coordinate system. Then the other trees are located exactly at the points of the integer lattice. If I shoot my rifle, the bullet follows a straight line. Since I am at the origin, that line will be y = mx for some slope m. All I have to do is pick m so that the line doesn’t pass through any lattice point.”

How can he pick such an m?