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

An Introduction to Basic Diophantine Equations

```Date: 08/27/2007 at 02:33:59
From: Katie
Subject: Diophantine equations

2 legged birds and 1 legged birds in a birdcage equaling 11 legs. What
different combinations could there be to make 11 legs.

I have never done Diophantine equations before and don't know how.

```

```
Date: 08/27/2007 at 12:38:00
From: Doctor Greenie
Subject: Re: diophantine equations

Hi, Katie.

This is a nice problem for looking at and understanding how
Diophantine equations can be solved.

Of course, by far the easiest way to solve this problem is to make a
list of all the possible combinations.  The numbers are small enough
that it should be easy to figure out.  So we'll first go ahead and
solve it that way; then we will look at the solution using Diophantine
equations and see the similarities between the two approaches.

Suppose we let x be the number of 2-legged birds and y be the number
of 1-legged birds.  Then the total number of legs is

2x + y

and we need to solve the equation

2x + y = 11

for all the solutions (x,y) that are non-negative integers.

Let's do that by "trial and error", using logic to tell us what kinds
of numbers to try.  We will first find all the possible combinations
by choosing different values of x in this equation--i.e., different
numbers of 2-legged birds.

number of  number of  remaining  number of
2-legged    legs on    number    1-legged
birds       these     of legs     birds
-------------------------------------------
0            0      11-0 = 11    11
1            2      11-2 = 9      9
2            4      11-4 = 7      7
3            6      11-6 = 5      5
4            8      11-8 = 3      3
5           10      11-10 = 1     1

So our complete set of solutions (x,y) is

(0,11), (1,9), (2,7), (3,5), (4,3), and (5,1)

Now let's look at an algebraic solution, which is similar.  This one
does not use Diophantine equations; but seeing the similarity between
the "trial and error" solution and the formal algebraic solution will
be helpful when we get to the Diophantine approach later.

Our beginning equation again is

2x + y = 11

We can solve this for "y":

y = 11 - 2x

Now we can choose non-negative integer values for x and find the
corresponding values for y; and we can do this as long as the value
we find for y is also a non-negative integer.

x   y = 11 - 2x
---------------
0   11 - 0 = 11
1   11 - 2 = 9
2   11 - 4 = 7
3   11 - 6 = 5
4   11 - 8 = 3
5   11 - 10 = 1

Now let's go back to the "trial and error" approach but this time
we'll start by choosing numbers of 1-legged birds instead of choosing
numbers of 2-legged birds, as we did above.  Then we will look at the
corresponding solution using algebra; this time we WILL use
Diophantine equations.

number of  number of  remaining  number of
1-legged    legs on    number    2-legged
birds       these     of legs     birds
---------------------------------------------------------------
0          0         11     11/2  --  oops!  not an integer
1          1         10     10/2 = 5
2          2          9      9/2  --  oops!
3          3          8      8/2 = 4
4          4          7      7/2  --  oops!

At this point, we can see that any choice of an even number of
1-legged birds is not going to give us a solution, because the
remaining number of legs will be odd, and no number of 2-legged birds
will have a total number of legs that is odd.  So we can save some
time by not bothering with the even values for the choices for x.

5          5          6      6/2 = 3
7          7          4      4/2 = 2
9          9          2      2/2 = 1
11         11          0      0/2 = 0

Of course, we again end up with our same set of solutions:

(0,11), (1,9), (2,7), (3,5), (4,3), and (5,1)

Now let's look at the corresponding algebraic solution, using
Diophantine equations.  Our original equation is still

2x + y = 11

But this time we will solve this equation for x instead of y:

2x + y = 11
2x = 11 - y
2x = (10 + 1) - y
2x = 10 + (1 - y)
x = 5 + (1 - y)/2

In the above work, a technique is used which is basic to one method
for solving Diophantine equations.  After we got the "x" term
isolated on the left-hand side and saw that it had a coefficient of
2, we rearranged the terms on the right so that "as much as
possible" of the right-hand side would be divisible by 2--so that,
when we divide by 2 to find an expressions for "x" alone, we get
integer results for as much as possible on the right-hand side.

So now our equation is

x = 5 + (1 - y)/2

and our x and y values are restricted to non-negative integers.  On
the left-hand side of this equation, "x" is an integer; and on the
right-hand side, "5" is an integer.  In order for the equation to be
satisfied, the term "(1 - y)/2" must also be an integer.  If (1 - y)/2
is to be an integer, then (1 - y) must be an even integer; and that
means y must be an odd integer.  And since y must be non-negative,
our possible values for y are 1, 3, 5, ....

So now we try these values for y, remembering that the corresponding
value we get for x also has to be a non-negative integer:

y   x = 5 + (1 - y)/2
---------------------
1   5 +  0/2 =  5 + 0 = 5
3   5 + -2/2 =  5 - 1 = 4
5   5 + -4/2 =  5 - 2 = 3
7   5 + -6/2 =  5 - 3 = 2
9   5 + -8/2 =  5 - 4 = 1
11   5 + -10/2 = 5 - 5 = 0

And once again we find the same set of solutions for (x,y):

(0,11), (1,9), (2,7), (3,5), (4,3), and (5,1)

I will show another example of solving Diophantine equations so you
can see one more time the process which is used.  But before I do
that, let's look again at our original equation and at the
solutions we found.  The equation is

2x + y = 11

and the solutions we found are

(0,11), (1,9), (2,7), (3,5), (4,3), and (5,1)

Look at these solutions, and compare each one in the list to the next
one.  Each time x increases by 1, the value of y decreases by 2.

Now let's look at the original equation and see why this makes sense.
Our equation says that 2 times x plus y has to equal 11.  Each time we
increase x by 1, the value of "2 times x" increases by 2.  If the sum
has to remain 11, then the value of y has to decrease by 2.

So instead of the formal algebraic process of using Diophantine
equations to find the solution to your problem, we can find, by trial
and error, ANY solution; then we can find all the other solutions by
either adding 1 to x and subtracting 2 from y or by subtracting 1 from
x and adding 2 to y.  For example, if the first solution we found
happened to be

(x,y) = (2,7)

then we could find the solutions for larger values of x by adding 1
to x and subtracting 2 from y...

(2,7), (3,5), (4,3), (5,1)

and we could find the solutions for smaller values of x by
subtracting 1 from x and adding 2 to y...

(2,7), (1,9), (0,11)

Now let's look at an arbitrary--and slightly more difficult--example
of a Diophantine equation and take one more close look at the formal
algebraic process for solving it.

3x + 11y = 100

We solve the equation for x:

3x + 11y = 100
3x = 100 - 11y

We want to "play" with the right-hand side so that, when we divide by
3 to get "x" by itself on the left, as much as possible of the
right-hand side will be integers.

3x = 100 - 11y
3x = (99 + 1) - (12y - y)
3x = 99 + 1 - 12y + y
3x = (99 - 12y) + (1 + y)
x = (33 - 4y) + (1 + y)/3

Now "x", "33", and "4y" are integers, so "(1 + y)/3" must be an
integer.  The non-negative integer values of y for which (1 + y)/3 is
an integer are

2, 5, 8, 11, ...

So we try each of these values in our equation for x in terms of y:

y   x = 33 - 4y + (1 + y)/3          (check this solution...)
----------------------------------------------------------------
2   33 -  8 + 3/3 = 25 + 1 = 26   3(26) + 11(2) = 78 + 22 = 100
5   33 - 20 + 6/3 = 13 + 2 = 15   3(15) + 11(5) = 45 + 55 = 100
8   33 - 32 + 9/3 =  1 + 3 =  4   3(4)  + 11(8) = 12 + 88 = 100

The next possible value of y (y = 11) will give us a negative value
for x, so we are done.  The set of solutions is

(x,y) = (26,2), (15,5), (4,8)

Note again how the solutions are related to the coefficients in the
original equation.  The equation is

3x + 11y = 100

Once we find one solution, we know we can find another solution by
either adding 11 to x and subtracting 3 from y, or by subtracting 11
from x and adding 3 to y.

So we could find the complete set of solutions for this example by
finding one solution by trial and error and then using this process
to find the remaining solutions.  For this particular example, we
might simply start trying different values for y until we find one
which gives us an integer value for x...:

y = 1; 3x + 11 = 100; 3x = 89  no, 89 is not divisible by 3
y = 2; 3x + 22 = 100; 3x = 78  yes, 78/3 = 26

So our "first" solution is (x,y) = (26,2)

And then we find our other solutions by subtracting 11 from x and
adding 3 to y, until we run into negative values for x:

(26,2), (15,5), (4,8)

Note that this "quick" process for finding all the solutions--by
finding an initial solution by trial and error and then using the
coefficients of the original equation to find the remaining solutions
--CAN be useful for relatively simple examples.  But the general
algebraic process for solving Diophantine equations is still very
useful, because in more difficult problems (with large coefficients
for x and y) finding an initial solution by trial and error can be
very difficult.

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 Algorithms
College Number Theory
High School Basic Algebra
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