Most of us have encountered simple equations such as 5x + 3y = 10. We know (or we may have a vague recollection from our school days) that if there are two unknown values (or 'variables'), you need two equations to be able to get a unique answer for x and y. With only one equation, absolutely any value of x can be used and a corresponding value of y can be calculated, which is not normally very useful.

Diophantine equations are different. They are named after the Greek mathematician, Diophantus of Alexandria, who lived in the 3rd century and developed many of the principles of number theory. In this sort of equation, there is a restriction that all the numbers involved must be whole numbers without any fractional or decimal part. That is, they must have an integer value. Finding values of x and y that fit these conditions can be much more difficult, but as a result is usually more useful.

Consider the following problem...

A bag of sugar weighs 5 pounds. A sack of oranges weighs 17 pounds. A box contains some sacks of oranges and some bags of sugar. The total weight of the box's contents is 103 pounds. What's in the box?

In normal algebraic terms the above problem is written 5x + 17y = 103 and has no unique solution, because there are two variables but only one equation. Treated as a Diophantine equation, however, it can provide a satisfactory solution, because we know that the numbers involved must be integers.

This particular problem imposes an additional restriction, that the numbers must be positive. Obviously we can't accept a solution where there is a negative number of bags of sugar. Normally when solving Diophantine equations, we allow such negative solutions. When we have found all the solutions, we can search among them for the ones that match the additional restrictions, like being positive.

Are They Always Soluble?

It is easy to see that the equation 4x + 2y = 101 has no solution for integer values of x and y. Both 4x and 2y must be even numbers so their sum must also be even, and 101 is an odd number so there can be no solution. It is because the 4 and the 2 share a common factor (2) which is not a factor of the 101 that there is no solution. In general, the equation ax + by = c (where a, b and c are constants) will have no solution if a and b have a common factor but don't share it with c.

On the other hand, if a and b have no common factors, then ax + by = c will always have a solution. In fact it will have an infinite number of solutions.

The case where all three terms share common factors should be simplified, by dividing each side by all the common factors until you arrive at one of the two cases just mentioned.

Once you have found a solution to ax + by = c, let's call it x₁ and y₁, you can arrive at another solution by adding b to x₁ and subtracting a from y₁. This is because this has the effect of adding a*b to the left side of the equation and then subtracting it again. Equally, you can subtract b from x₁ and add a to y₁. By repeating these operations as often as necessary, you can get all of the infinite number of solutions to the equation.

Methods of Solving Simple Diophantine Equations

If one of the variables has a coefficient of 1, that is, if one of the variables stands on its own as a bare x or y with no number multiplied by it, then the equation can be easily solved. We can simply let the other variable take any value we like! For example, the equation:

23x + y = 103

can be rewritten as:

y = 103 - 23x

We can now let x equal anything we like and calculate the corresponding value of y. One such solution is x=3, y=34.

When neither of the variables has a coefficient of 1, things are not as straightforward.

Trial and Error

A simple equation like 5x + 17y = 103 where the numbers are small is often best solved by trial and error. You can rewrite the equation as 5x = 103 - 17y. Try out a few different possible values for y, starting with y = 0 and see if you can find one that fits. Suppose that we want a solution where both x and y are positive:

• y = 0, 5x = 103 - 0 = 103, not a multiple of 5
• y = 1, 5x = 103 - 17 = 86, not a multiple of 5
• y = 2, 5x = 103 - 34 = 69, not a multiple of 5
• y = 3, 5x = 103 - 51 = 52, not a multiple of 5
• y = 4, 5x = 103 - 68 = 35, Yes! It's a multiple of 5, being 5*7
• y = 5, 5x = 103 - 85 = 18, not a multiple of 5
• y = 6, 5x = 103 - 102 = 1, not a multiple of 5
• y = 7, 5x = 103 - 119 = -16, negative so we've gone far enough!

So with y = 4, we get x = 7.

In these days of fast computers and spreadsheets, it is a very simple job to test a few thousand values to find one that fits. We can extend the method shown here to equations with much bigger numbers involved, trying out possible values of x from 0 to, say, 10,000. This approach takes less than a minute's work to set up on a spreadsheet and immediately gives a solution. It works well where the values of a and b are not too big.

If the values of a and b are really big, say bigger than 100,000, you might not find a solution by trial and error.

Reduction to a Simpler Form

Consider the equation:

47x + 23y = 103

It can be simplified. Note that 47 is greater than 23, so we can divide 47 by 23. We get 2 with a remainder of 1. So 47 = 23*2 + 1. The equation can be rewritten as:

(23*2 + 1)x + 23y = 103

or

23(2x + y) + x = 103

Now if we define a new variable z by z = 2x + y we can rewrite the equation as:

23z + x = 103

This is a simpler equation to solve and it has already been shown how to solve it: one solution is z=3, x=34. We can work back from z to get y = -65.

A General Method for First Order Equations With Two Variables

The simplification process can be extended to make a general method for solving Diophantine equations with two variables. First order means that none of the variables have a power greater than 1; there are no x² terms. Instead of using x, y and z as names for variables, the general method uses x₁, x₂, x₃ etc. That way, we don't run out of variable names!

Proceed as follows:

• Write the equation in the form ax₂ + bx₁ = c where a is bigger than b.

• Divide the bigger coefficient, a, by the smaller one, b giving a quotient q and a remainder r.

• Rewrite the equation replacing a with q*b + r.

• Regroup the equation so that the left hand side is q*term + value*x₂.

• Introduce a new variable x₃ to replace 'term' in that equation.

You now have two equations: one is a simplified version of the original equation, the second is a method for getting x₃ from x₂ and x₁.

Repeat this process as often as necessary, introducing new variables x₄, x₅ etc, until one of the two coefficients is 1. The equation can then solved as above. Working backwards, we can calculate all the x's along the way until we eventually reach x₁ and x₂.

A Cumbersome Solution

Not only is this method cumbersome, but the solution it gives is often very large, although it is a valid solution to the equation. For example, applying it to the equation in the puzzle about bags of sugar and oranges, we get:

17x₂ + 5x₁ = 103
(5*3+2)x₂ + 5x₁ = 103
5(3x₂ + x₁) + 2x₂ = 103
5x₃ + 2x₂ = 103 [where x₃ = 3x₂ + x₁]
(2*2+1)x₃ + 2x₂ = 103
2(2x₃ + x₂) + x₃ = 103
2x₄ + x₃ = 103 [where x₄ = 2x₃ + x₂]

One solution is:

x₄ = 0
x₃ = 103
x₂ = -206
x₁ = 721

The solution, with 721 bags of sugar and minus 206 sacks of oranges is not satisfactory. The numbers are too large and we don't want negative oranges. (They'd give you scurvy!)

We can reduce this solution to a more manageable one by adding 5 to x₂ and subtracting 17 from x₁. This gives another solution to the equation. We can do this as many times as necessary. A quick calculation shows that we'll have to add 5 to -206 a total of 42 times to make it positive. This give us -206 + 42*5 = 4. At the same time, we must subtract 17 from 721 a total of 42 times: 721 - 42*17 = 7.

So our final solution is that x₁=7 and x₂ = 4, so there are 7 bags of sugar and 4 sacks of oranges in the box.