Diophantine Equations, Step by Step

Date: 10/01/2002 at 12:00:29
From: Jennifer 
Subject: Finding all positive integer solutions

Find all positive integer solutions to 43x + 7y + 17z = 400

Date: 10/01/2002 at 14:37:30
From: Doctor Greenie
Subject: Re: Finding all positive integer solutions

Hello, Jennifer -

This problem gives you a lot of exercise in solving diophantine 
equations. Diophantine equations are ones in which you have fewer 
equations than unknowns and the values of the unknowns are restricted 
to integer values.

Probably the most common type of problem involving diophantine 
equations is one in which there are three unknowns and you only have 
two equations. Your problem is more involved, since we have three 
unknowns and only one equation.

To solve this type of problem, we simply choose, one at a time, all 
the possible values for one of the unknowns; for each of those values 
we get a diophantine equation with two unknowns, which we then solve 
using standard methods for diophantine equations.

I will help get you started on this process, in case you are not 
familiar with those standard techniques.

Because the coefficient on x is the largest of the three coefficients, 
the number of possible values for x is less than for the other 
unknowns. Because of this, we will have fewer cases to consider if we 
start our solution by considering the different possible values of x.  
43*9 is less than 400 and 43*10 is greater than 400, so the range of 
values we need to consider for x is from 1 to 9.

I will just pick one of these 9 cases; each one is solved in a manner 
similar to what I will show for that one case.

The case I will work through is the case where x=3.  Given x=3, our 
equation is

  43(3)+7y+17z = 400
  129+7y+17z = 400
  7y+17z = 271

Now for a demonstration of the standard method for solving 
diophantine equations....

We take our equation in its current form and solve for one variable 
in terms of the other. It doesn't matter which variable you solve for.  
One way may lead to much simpler arithmetic later on than the other; 
with some experience, you might be able to predict which is the better 
way to go. I won't deal with that question here; I'm simply going to 
choose to solve for y in terms of z.

  7y+17z = 271

  7y = 271-17z

      271-17z
  y = -------
         7

         5   17z
  y = 38 - - ---
         7    7

           17z-5
  y = 38 - -----
             7

In the preceding work, I could have stopped when I got the equation

      271-17z
  y = -------
         7

However, with the equation in this form, finding values of z that make 
the expression on the right an integer is difficult because of the 
large numbers. The work I need to do to finish the analysis for this 
case will be easier if I take the whole number part out of the 
expression on the right. In the last form of the equation above, since 
y needs to be an integer and since 38 is an integer, I know that the 
expression

  17z-5
  -----
    7

must also be an integer.

At this point, I just start trying values of z until I find one for 
which (17z-5) is a multiple of 7.  Starting with z=1, z=2, etc., I 
find the following values for (17z-5):

  12, 29, 46, 63, ...

"63" is the first of these which is a multiple of 7; this gives me my 
first solution for this case:

  z=4; 17z-5=63; (17z-5)/7=63/7=9; y=38-9=29

The first solution I have found to the problem is

  (x,y,z) = (3,29,4)

At this point, I can continue trying values of z=5, z=6, ..., and so 
on; but I can be smarter than that.  In the expression

  17z-5
  -----
    7

the "17" and the "7" have no common factors; this tells me that, 
after the solution with z=4, my next possible solution will be with 
z=4+7=11. Trying this solution, I find

  z=11; 17z-5=182; (17z-5)/7=182/7=26; 38-26=12

And so the second solution I have found to the problem is

  (x,y,z) = (3,12,11)

The next possible solution for this case should be when z=11+7=18; 
trying this solution, I find

  z=18; 17z-5=301; (17z-5)/7=43; y=38-43=-5

This attempt to find another solution gives me a negative value for y, 
so it is not a valid solution. This means I have found all the 
solutions for the case x=3.

Note that there is one more place I can be smart to cut down on the 
amount of work I need to do. Once I have found my first solution for 
this case,

  (x,y,z) = (3,29,4)

I can again look at the expression

           17z-5
  y = 38 - -----
             7

and see that, when I increase z by 7, my y-value is going to decrease 
by 17. So then I can find all my other solutions for the case x=3 
simply by adding 7 to my z-value and subtracting 17 from my y-value 
until the y-value becomes negative:

  1st solution:  (3,29,4)
  2nd solution:  (3,12,11)
  3rd solution:  (3,-5,6)  (invalid...)

So......

There are 2 solutions to the problem when x=3. You need to go through 
this entire process for each of the other cases from x=1 to x=9 to 
find the complete set of solutions.

It isn't really as much work as it sounds. For example, for the case 
x=9, the "43x" is nearly the whole total of 400, and it turns out 
there are no values of y and z that satisfy the original equation.  
And when you are done with the whole problem you will have had a lot 
of experience solving diophantine equations.

I hope all this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/