Diophantine Equations

Diophantine Equations

A Diophantine equation is one in which the solutions must be integers or rational numbers. On this page we shall restrict ourselves to solutions in positive integers.

Let us imagine one's experience on his first encounter with the following puzzle:

There's Dad and Ma and Brother and Me;
The sum of our ages is eighty-three.
Six times Dad's age is seven times Ma's
And she is three times Me.

How old is Dad?

The ordinary algebra student says, "Hey, I can't solve these equations because there are four unknowns and only three equations." Indeed there is no unique solution over the field of the real numbers, but there is a unique solution in integers. Here is another problem of the same sort:
At Jimmy's school four-fifths of the students use five-sixths of the desks. What is the smallest possible number of students in the class?
Take these problems to school, bring them up in math class, and watch Teacher slowly turn into a babbling idiot.

Before turning to the formal theory of Diophantine equations, let us see what a little common sense will do.

Lines 3 and 4 of the poem let us write the ages of Dad, Ma and Me in terms of an arbitrary integer k.

D = 7k
M = 6k
E = 2k
Next we inquire as to the possible values of k. To find the largest possible value of k we add up the coefficients in the above expressions, divide into 83 and get 5 with a remainder of 8. k = 5 works pretty well, giving Dad as 35, Ma as 30, Me as 10 and Brother as 8. K = 4 wouldn't work since that would make Brother 53, older than either Mom or Dad. In this case we found a feasible solution on the very first try, and it is the only solution because of the unstated but assumed constraint that children cannot be older then their parents. Actually, this is a very easy problem. Now for the desks at school.

The first thing one notices is that the number of students must be divisible by 5 and the number of desks must be divisible by 6. Let j and k be two arbitrary integers of value 1 or greater and let 5j be the number of students and 6k be the number of desks.

Let the students enter the classroom. Now at the teacher's command let four-fifths of the students sit down at five-sixths of the desks. Four fifths of the students is 4j and five sixths of the desks is 5k. Since these numbers must be the same, we have 4j = 5k and the ratio j/k is 5/4. The smallest numbers with this ratio are j = 5 and k = 4. That would make the number of students 25 and the number of desks 24. Let us try these numbers in the problem. Four fifths of the students (20) use five sixths of the desks (20). Since these numbers are the same, we have solved the problem. The fact that there is one more student than there are desks shouldn't matter since at no point are we told that all of the students sit down at the same time.

Aren't we smart!

The subway train had a minimal number of passengers. When it got to Liberty Street three quarters of the passengers got out and seven people got on. At the next two stops, Church Street and Canal Street, exactly the same thing happened. How many got off at Canal Street?

The following problem is more difficult and uses concepts from the theory of probability as well as from the theory of Diophantine equations.

"Take any two guys from the holding pen," says Sgt. Mulvaney, "And it's 50-50 that at least one of them will have a criminal record." How many prisoners could be in the the holding pen and how many have criminal records?

She Made a Mistake

A woman counted her eggs by threes and found that there were two over and then again by sixes and found that there were three over. Show that she made a mistake.