Greek mathematician Diophantus of Alexandria.
Let’s imagine Great Aunt Christine is going for her annual holiday to Barbados.
She sends her butler John down to the airport with her collection of suitcases,
each of which weighs either 18 or 84 kilograms, and is informed that the total
weight checked-in is 652 kilograms. When he arrives back in Belgravia, John’s
nine-year-old son James pipes up ‘that can’t be right, because the gcd 6 doesn’t
divide into 652’. James suggests that the correct total weight might actually be
642 kilograms.
James knows that there is a solution in whole numbers to the equation 18x +
84 y = c if and only if the gcd 6 divides the number c. It does not for c = 652 but
it does for 642. James does not even need to know how many suitcases x, y of
either weight Aunt Christine intends to take to Barbados.
The Chinese remainder theorem
When the gcd of two numbers is 1 we say they are ‘relatively prime’. They
don’t have to be prime themselves but just have to be prime to each other, for
example gcd(6, 35) = 1, even though neither 6 nor 35 is prime. We shall need
this for the Chinese remainder theorem.
Let’s look at another problem: Angus does not know how many bottles of
wine he has but, when he pairs them up, there is 1 left over. When he puts them
in rows of five in his wine rack there are 3 left over. How many bottles does he
have? We know that on division by 2 we get remainder 1 and on division by 5
we get remainder 3. The first condition allows us to rule out all the even
numbers. Running along the odd numbers we quickly find that 13 fits the bill (we
can safely assume Angus has more than 3 bottles, a number which also satisfies
the conditions). But there are other numbers which would also be correct – in
fact a whole sequence starting 13, 23, 33, 43, 53, 63, 73, 83,...
Let’s now add another condition, that the number must give remainder 3 on
division by 7 (the bottles arrived in packs of 7 bottles with 3 spares). Running
along the sequence 13, 23, 33, 43, 53, 63,... to take account of this, we find
that 73 fits the bill, but notice that 143 does too, as does 213 and any number
found by adding multiples of 70 to these numbers.
In mathematical terms, we have found solutions guaranteed by the Chinese
remainder theorem, which also says that any two solutions differ by a multiple of