Diophantine problems for garden gnomes

Suppose you are asked to solve the equation

$25x+11y=177.$

There are two unknowns and only one equation, so you’ll get infinitely many solutions. Rearranging, you get

$y=(177-25x)/11,$

so you know what shape these solutions take.

"How many bricks do I need?"

But now suppose you're asked to find a particular solution $(x,y)$ such that both $x$ and $y$ are positive whole numbers and their sum is as small as possible. You could use trial and error to find the solution (if it exists), but this is mathematics, and in mathematics we like a bit of method and order. Fortunately, one method for integer solutions came out of Alexandria in about 250 AD. But, before we get into that, let's add a little context to make things more interesting.

Mr and Mrs Magnus are a happy gnome couple. Unfortunately, foreseeing that they will be unable to keep up with their rising mortgage repayments, they've been forced to move into my back garden (where salaries are much higher). However, they have been presented with some trouble in building their new home. Gnome by-laws state that the total number of bricks used in any construction project must be 177 or planning permission will not be granted.

As gnome houses form roughly the shape of a triangular prism and one wall (namely the garden fence) is already in place, only two walls need to be built. The plot of land they have acquired is shown below with all dimensions measured in bricks.

The question is, what is the smallest number of bricks they have to buy to comply with the local council, yet not waste any money?

Luckily, Mr and Mrs Magnus’ son, Zurich, knows a thing or two about numbers. As his parents discuss their dilemma over tea, Zurich writes out an equation:

$25x+11y=177,$

where $x$ and $y$ are the height in bricks of the two respective walls. Chuffed with himself, he shows his parents and receives a solemn "that’s nice dear".

Duly encouraged, Zurich sits and thinks about how to solve this equation. The secret here is that you cannot have half a brick: $x$ and $y$ must be integers. (This, by the way, rules out that the two walls have the same height, ie that $x=y$ , because

$25x+11x=36x=177$

gives that $x=117/36$ , which isn’t a whole number.)

Now, Zurich has recently been reading Euclid’s Elements before he goes to bed and so has just found out about a nifty trick called Euclid’s algorithm, which finds the highest common factor of two numbers, $r_1$ and $r_2$ . We assume $r_1 > r_2$ . First divide $r_1$ by $r_2$ and take the remainder, calling it $r_3$ . Then divide $r_2$ by $r_3$ , and take the remainder, calling it $r_4$ . Keep repeating this process and eventually you get a remainder of zero. The last non-zero remainder is the highest common factor of the original two numbers.

So, Zurich lets $r_1 = 25$ and $r_2 = 11$ from our previous equation. He then performs the algorithm with some zest. At each step, he keeps track of the calculation by writing $r_ i-q r_{i+1}=r_{i+2}.$ Here $r_ i$ is the number that's being divided at that step, $r_{i+1}$ is the number it's being divided by and $r_{i+2}$ is the corresponding remainder:

This tells him that the highest common factor is 1 (if he goes any further he will reach zero). Fortunately this is what we would expect, as 11 is a prime number. Now he uses the equations that he has just generated to write out a true statement equal to 1 that involves 25 and 11.

$3 - 2 \times 1 = 1$

$(25 - 11 \times 2) - (11 - 3 \times 3) = 1$

He keeps 25 and 11 as separate factors, so:

$25 - 11 \times 3 + 3 \times 3 = 1$

$25 - 11 \times 3 + 3(25 - 11 \times 2) = 1$

$25 + 25 \times 3 - 11 \times 3 - 11 \times 6 = 1$

Collecting terms:

$25 \times 4 - 11 \times 9 = 1$

Let’s compare that to the original:

$25x + 11y = 177.$

So, Zurich rewrites his sum as:

$25(4) + 11(-9) = 1$

Now, that’s all very well and good, but it needs to equal 177 not 1, so still treating 25 and 11 as terms, he multiplies the whole equation by 177:

$25(4 \times 177) + 11(-9 \times 177) = 177.$

Some quick multiplication leaves him with:

$25(708) + 11(-1593) = 177.$

This is a perfectly legitimate answer, but sadly it is very difficult to come by negative bricks these days, and it certainly doesn't look like the smallest answer. So, Zurich ponders how to make $y$ positive without changing the sum of the equation from 177. To make the coefficient of 11 positive, he needs to add some multiple of 11, say $11n$ , to the left hand side of the equation. To keep the equation true, he needs to take this multiple away again:

$25(708)+11(-1593)=25(708)+11(-1593+n)-11n=177.$

To get the equation into the required form, he writes

$25(708-11n/25)+11(-1593+n)=177.$

Since $11n/25$ must be a whole number, he nows that $n$ must be a multiple of $25$ . Say $n=25t$ for some $t$ . This gives

$25(708-11t)+11(-1593+25t)=177.$

So now Zurich only needs to find a number $t$ so that $-1593+25t$ is greater than zero but as small as possible. Dividing 1593 by 25 using long division he gets:

Therefore, the number he is looking for is $t=64$ , giving

$25(708 - (64 \times 11)) + 11(-1593 + (64 \times 25)) = 177$

$25(708 - 704) + 11(-1593 + 1600) = 177$

$25(4) + 11(7) = 177.$

Zurich compares this to the original problem and finds that the solution is $x = 4$ and $y = 7.$ The problem is solved just as his parents finish their tea.

Diophantine equations

Generally, equations of the form

$ax+by=c,$

where the variables $x$ and $y$ are only allowed to be whole numbers are called linear Diophantine equations after the great Greek arithmetician Diophantus, who dealt with many such problems in his works.

If $c$ is a multiple of the greatest common divisor of $a$ and $b$ , then an equation of this form has an infinite number of solutions. This is the case in our example equation, where $a=25$ , $b=11$ and $c=117$ , with the greatest common divisor of $a$ and $b$ being 1. The further constraint that the solutions must be positive and their sum as small as possible then gave us the particular result. If $c$ isn’t a multiple of the highest common factor of $a$ and $b$ , then the equation has no integer solutions at all.

There are also diophantine equations of higher degree, for example

$x^ n+y^ n=z^ n,$

where $x$ , $y$ and $z$ are the variables and $n$ is a constant. The statement that no integer solutions exists when $n>2$ is Fermat’s famous last theorem, which remained unproved for over 400 years.

(It was in the margin of his copy of Diophantus' book Arithmetica that Fermat wrote his renowned lines. See the Plus article Fermat's last theorem and Andrew Wiles for more information.)

In terms of practical applications, being able to solve this sort of problem is surprisingly useful even in the modern world. The classic example is working out how many men, women and children attended a show given only the price of each ticket and the final takings. Plus, if you are that way inclined, certain types of puzzles in magazines and newspapers can suddenly become a whole lot simpler with this under your belt. From business to coffee breaks, exploring number theory to building your house, it's definitely a technique worth knowing!

P.S. In his excitement, Zurich forgot to make an allowance for the front door in one of the walls. Luckily, his skilled father was able to make a chimney out of the extra bricks at the same time as close the gap that must be created where the two walls and the roof join.

About the author

Emily Woodhouse is in her final year at Devonport High School for Girls in Plymouth. Her favourite day at school is triple maths, double chemistry and she thinks anyone who doesn't like numbers is absolutely mad. Most likely to be found in the depths of Dartmoor, hiking and discussing numbers with its resident gnomes are among her favourite pastimes. Unsurprisingly, she is applying to read mathematics at university. One of her aims in life is to be called a mathematician.