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
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
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:
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:
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?
Hmm, this time it looks like we get solutions only if c is a multiple of 3. How about 5x + 8y = c?
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 ______." |