Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Linear Equations
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search