## 2.3   Linear Diophantine Equations 1

As stated in the Prelab section, one goal of this chapter is to develop a systematic method for finding all integer solutions x and y (when there are any) to the linear diophantine equation

ax + by = c,                     (1)

where a, b, and c are integer constants. As you discovered when working on the Prelab exercises, for a given choice of a and b, equation (1) may have several solutions or possibly no solutions; it depends on the value of c. If we have specific values for a and b, how can we figure out the values of c for which equation (1) will have a solution? As a first step, let's look at the situation for a specific choice of a and b, say a = 6 and b = 4. In this case, the above equation becomes

6x + 4y = c,                     (2)

and our question is: For what values of c is there a solution to this equation? One way to approach this is to try plugging a bunch of different values for x and y into the left-hand side of (2), and see what we get out. After all, any value that comes out must be a suitable value for c. (Do you see why?) Below is an applet programmed to automatically do the "plugging in." It is initially set to compute the values of 6x + 4y for each choice of x and y satisfying –3 x 5 and –3 y 5:

Your browser does not support java.

On the basis of this list, it looks like c must be an even integer in order for equation (2) to have a solution. We can also see that some values appear several times; this indicates that for a given value of c there may be lots of solutions.

If we think about it, if x = m and y = n are solutions to 6x + 4y = c, then x = -m and y = –n are solutions to 6x + 4y = –c. Therefore, if we know the positive values of c for which there are solutions to equation (2), then we also know the story for negative values of c. (Of course, c = 0 is easy. Quick, name choices for x and y such that 6x + 4y = 0.) Thus, we can restrict ourselves to c > 0.

Below is an applet that will compute ax + by for specified values of a and b (plugging in x and y satisfying –n x n and –n y n), and then removes the repeated and nonpositive values. Here is what we get when we try it out on our equation, which corresponds to a = 6 and b = 4:

Your browser does not support java.

As we observed above, it looks like c must be a multiple of 2 in order for equation (2) to have a solution. Let's try a different equation, say 9x + 12y = c. What do we get in this case?

Your browser does not support java.

Hmm, this time it looks like we get solutions only if c is a multiple of 3. How about 5x + 8y = c?

Your browser does not support java.

#### Research Question 2

Execute the above applet again using values of a and b of your choosing until you have enough data to fill in the blank at the end of the following conjecture:

"In order for ax + by = c to have solutions, c must be of the form ______."

Section 2.1 | Section 2.2 | Section 2.3 | Section 2.4 | Section 2.5