Can You Buy 100 Birds with 100 Coins?

Play with the market before reading on. Try these, in order.

• a.Find one answer by any means. (A hint if you are stuck: try 4 roosters.)
• b.Find an answer with no roosters.
• c.Try every number of roosters from 0 to 12. Which numbers of roosters ever give an answer?
• d.Put your answers in a table, roosters going up. What happens to the hens each time? To the chicks?

The market gives you two facts and asks for three numbers. Call them r roosters, h hens and c chicks:

$$r + h + c = 100 \qquad\text{(birds)}$$
$$5r + 3h + \tfrac{c}{3} = 100 \qquad\text{(coins)}$$

You met two equations in two unknowns in Grades 8 and 9, and they usually have just one answer. With three unknowns there is room to spare, so we get rid of the chicks. Multiply the coins equation by 3, so that every term is a whole number, then take away the birds equation:

$$15r + 9h + c = 300$$
$$(15r + 9h + c) - (r + h + c) = 300 - 100$$
$$14r + 8h = 200, \quad\text{so}\quad 7r + 4h = 100.$$

One equation in two unknowns, roosters and hens. With any numbers allowed, it has an endless line of answers: choose r, then h = (100 − 7r)/4. The puzzle’s extra rule is what makes it a puzzle: only whole numbers.

Now look at 7r + 4h = 100 with whole numbers in mind. 4h is a multiple of 4, and so is 100. So 7r must be a multiple of 4 too. 7 and 4 have no common factor, so the 4 has to come from r itself: the roosters must be a multiple of 4. Write r = 4t for a whole number t. Then

$$28t + 4h = 100, \quad h = 25 - 7t, \quad c = 100 - r - h = 75 + 3t.$$

There is the swap, out of the algebra: each step of t adds 4 roosters, takes 7 hens and adds 3 chicks. The hens can’t go below 0, so 25 − 7t ≥ 0 and t is 0, 1, 2 or 3. Exactly four answers, and a proof that there are no more. And the chicks, 75 + 3t, always come out a multiple of 3, as the price “3 for 1 coin” needs.

An equation where only whole-number answers count is called a Diophantine equation, after Diophantus of Alexandria, a Greek mathematician of about 250 CE (see the story below). The simplest kind, two unknowns with whole-number coefficients,

$$ax + by = c,$$

is a linear Diophantine equation. The Hundred Fowls came down to one: 7r + 4h = 100.

Draw 7x + 4y = 100 on squared paper. It is a straight line, from (0, 25) on the y-axis to $(14\tfrac{2}{7}, 0)$ on the x-axis. Most of the points on it have fractions in them. The whole-number answers are the points where the line passes exactly through a corner of the squares, a lattice point.

Try these with the widget.

• a.Keep a = 7, b = 4 and move c. Are the whole-number points always evenly spaced?
• b.Set a = 6, b = 9. Find a value of c with no whole-number points at all, and one with several. What do the values with points have in common?
• c.Set a = 3, b = 5, c = 7. Why are there no points here, though the widget says the line does pass through some?

Why evenly spaced? Suppose (x₁, y₁) and (x₂, y₂) are both on 7x + 4y = 100. Take one equation from the other:

$$7(x_2 - x_1) + 4(y_2 - y_1) = 0, \quad\text{so}\quad 7(x_2 - x_1) = -4(y_2 - y_1).$$

The left side is a multiple of 7, so the right side is too; 4 has no factor 7, so y₂ − y₁ must be a multiple of 7. In the same way x₂ − x₁ is a multiple of 4. So two whole-number points are always a whole number of steps of 4 across and 7 down apart, and that step itself always works. That is the pattern of the market, seen as a picture.

When a and b share a factor, divide it out first. Write g for the highest common factor of a and b, their HCF (also called the greatest common divisor, gcd). Then the step is b/g across and a/g down: on 6x + 9y = 99, g = 3, and each step is 3 across and 2 down.

The widget’s 6x + 9y = 100 has no whole-number points anywhere, not even with negative numbers. The reason takes one line: whatever whole numbers x and y are, 6x + 9y = 3(2x + 3y) is a multiple of 3, and 100 isn’t. The same argument works for any equation.

The first part we have proved. The second needs more: when g divides c, how do we know there is even one solution, and how do we find it? For the Hundred Fowls a little trying was enough. For 17x + 23y = 1{,}000 trying is slow, and for the numbers a computer works with, hundreds of digits long, it is hopeless. The next section is the method, and it is one you already know half of.

In Grade 7 you found the HCF by the division method: divide the bigger number by the smaller, then the smaller by the remainder, and so on; the last remainder that isn’t 0 is the HCF. That method is more than 2,000 years old, and it has a name: Euclid’s algorithm, from Euclid’s Elements (about 300 BCE), though Euclid probably collected it from mathematicians before him. For 7 and 4:

$$7 = 1 \times 4 + 3$$
$$4 = 1 \times 3 + 1$$
$$3 = 3 \times 1 + 0$$

The HCF is 1. Now the trick: every remainder can be written as some 7s and some 4s. Read the lines upwards, writing each remainder from the line it came from:

$$3 = 7 - 4$$
$$1 = 4 - 3 = 4 - (7 - 4) = 2 \times 4 - 1 \times 7$$

So 7 × (−1) + 4 × 2 = 1: one solution of 7x + 4y = 1. This is Euclid’s algorithm run backwards (often called the extended Euclidean algorithm). It always works, because each remainder is the number before it minus some of the one before that; if those two are made of 7s and 4s, so is the remainder. The last remainder that isn’t 0 is the HCF, so the HCF itself is made of 7s and 4s.

The Hundred Fowls traveled too. Mahavira’s Ganita-sara-sangraha (850) asks for 100 birds of four kinds, pigeons, sarasa cranes, swans and peacocks, for 100 coins; Alcuin of York (about 735–804) set seven puzzles like it in Europe; and Abu Kamil, in Egypt around 900, wrote a whole Book of Birds on them.

Now turn the question round. Imagine a shop where the only coins are Rs 3 and Rs 5 (a made-up puzzle). Which amounts can be paid exactly? That asks for whole numbers x, y ≥ 0 with 3x + 5y = n: the same kind of equation, with n changing.

Rs 1, 2 and 4 can’t be paid; Rs 3, 5 and 6 can. Rs 7 can’t: 7 − 5 = 2 and 7 − 3 − 3 = 1 aren’t payable. Rs 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5. And once you can pay 8, 9 and 10, you can pay 11, 12, 13 by adding a Rs 3 coin to each, and so on for ever. So 7 is the largest amount you can’t pay, and there are exactly 4 amounts you can’t: 1, 2, 4 and 7.

The rows explain it. Every amount in a row leaves the same remainder when divided by the small coin a. Once a row has one payable amount, every amount to its right is payable too: add one more a-coin each step. So each row has a first payable amount, and that first one is always made of b-coins only (any a-coins in it could be taken away, giving a smaller payable amount in the same row). The first payable amounts are therefore

$$0,\ b,\ 2b,\ \ldots,\ (a - 1)b,$$

and they all fall in different rows (if two of them left the same remainder, their difference, a multiple of b smaller than ab, would be a multiple of a too, which can’t happen when a and b share no factor). The last row to start does so at (a − 1)b. The amount just before it in that row, (a − 1)b − a, can’t be paid, and every amount bigger than it can (every other row has already started). So:

Why exactly half of the amounts from 0 to ab − a − b? There is a neat pairing. Call N = ab − a − b, and pair each amount n with N − n: with Rs 3 and Rs 5, N = 7, and the pairs are 0 and 7, 1 and 6, 2 and 5, 3 and 4. In every pair, exactly one can be paid. They can’t both be payable, because then their sum, N, would be payable too. And if n can’t be paid, N − n can: Euclid’s algorithm run backwards gives whole numbers with n = ax + by, and stepping along the line, b at a time in x, brings x to between 0 and b − 1. Then y must be negative, since n isn’t payable, and N − n = a(b − 1 − x) + b(−1 − y), where both brackets are 0 or more. There are N + 1 = (a − 1)(b − 1) amounts from 0 to N, so half of them can’t be paid.

James Joseph Sylvester published the formula ab − a − b in 1882, and he also showed that (a − 1)(b − 1)/2 amounts can’t be paid. The question for three or more coins, the coin problem (or Frobenius problem), has no formula like it; with boxes of 6, 9 and 20 nuggets, the largest number you can’t buy is 43.

So far the unknowns stood alone, never squared. Square them, and whole-number questions change character.

• $x^2 + y^2 = 3$ has no whole-number solutions. Squares of whole numbers are 0, 1, 4, 9, …, and no two of them add to 3. (Looking at remainders on dividing by 4 shows more: a square leaves 0 or 1, so a sum of two squares never leaves 3; 3, 7, 11, 15, … are never sums of two squares.)
• $x^2 + y^2 = z^2$ has infinitely many: 3, 4, 5; 5, 12, 13; 20, 21, 29. Finding them all is topic 7.
• $x^2 - 2y^2 = 1$ has infinitely many too, 3 and 2, 17 and 12, 99 and 70, 577 and 408, but they grow fast and are hard to find by trying; Bhaskara II’s method for such equations is topic 36.

• Astronomy, long ago: Indian astronomers’ kuttaka found the days since the start of a yuga from a planet’s position (the fact above).
• Coins, stamps and packs: which amounts or quantities can be made from fixed sizes is the coin problem, answered by ab − a − b for two sizes.

• How Do You Find Every Right Triangle with Whole Sides? A Diophantine equation with squares, $x^2 + y^2 = z^2$, and a recipe that makes every answer.
• How Many Eggs Were in the Basket? Count in twos, threes, fours…: another old puzzle about remainders, the Chinese remainder theorem, solved with the kuttaka’s ideas.
• How Can Two Strangers Agree on a Secret in Public? Remainders, powers, and why Euclid’s algorithm run backwards is inside every secure website.
• How Did Bhaskara Solve Fermat’s Challenge 500 Years Early? $x^2 - 61y^2 = 1$ and the chakravala method.
• Which Amounts Can You Never Pay with 3s and 5s? (Grades 6–8) The coin puzzle by trial and pattern.
• Grade 10, Sequence and Series: the answers of a linear Diophantine equation are two arithmetic sequences side by side (roosters 0, 4, 8, 12; hens 25, 18, 11, 4).