As stated in the Prelab section, one goal of this chapter is to develop a systematic method for finding all integer solutions

xandy(when there are any) to the linear diophantine equationax+by=c, (1)where

a,b, andcare integer constants. As you discovered when working on the Prelab exercises, for a given choice ofaandb, equation (1) may have several solutions or possibly no solutions; it depends on the value ofc. If we have specific values foraandb, how can we figure out the values ofcfor which equation (1) will have a solution? As a first step, let's look at the situation for a specific choice ofaandb, saya= 6 andb= 4. In this case, the above equation becomes6 x+ 4y = c, (2)and our question is: For what values of

cis there a solution to this equation? One way to approach this is to try plugging a bunch of different values forxandyinto the left-hand side of (2), and see what we get out. After all, any value that comes out must be a suitable value forc. (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+ 4yfor each choice ofxandysatisfying –3x5 and –3y5:

On the basis of this list, it looks like

cmust 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 ofcthere may be lots of solutions.If we think about it, if

x=mandy=nare solutions to 6x+ 4y=c, thenx= -mandy= –nare solutions to 6x+ 4y= –c. Therefore, if we know the positive values ofcfor which there are solutions to equation (2), then we also know the story for negative values ofc. (Of course,c= 0 is easy. Quick, name choices forxandysuch that 6x+ 4y= 0.) Thus, we can restrict ourselves to c > 0.Below is an applet that will compute

ax+byfor specified values ofaandb(plugging inxandysatisfying –nxnand –nyn), and then removes the repeated and nonpositive values. Here is what we get when we try it out on our equation, which corresponds toa= 6 andb= 4:

As we observed above, it looks like

cmust 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

cis a multiple of 3. How about 5x+ 8y=c?

## Research Question 2

Execute the above applet again using values of

aandbof your choosing until you have enough data to fill in the blank at the end of the following conjecture:

"In order forax+by=cto have solutions,cmust be of the form ______."

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

Copyright © 2001 by W. H. Freeman and Company