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 
questions about any of this.

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