When they tried to divide the fortune into equal portions, 4 coins remained.
In the ensuing brawl over who should get the extra coins, one pirate was killed.
The wealth was then redistributed, but this time an equal division left 10 coins over.
Again an argument developed in which another pirate was killed.
But now the total fortune could be evenly distributed among the survivors.
What was the least number of coins that could have been stolen?
If x is the total number of coins, we can write down three congruences:
Can we find a number x that simultaneously satisfies these three congruences?
We’ll solve this puzzle later, but first we’ll need to solve linear congruences in general: these have the form , where n is a positive integer, a and b are given integers, and our task is to find the unknown x. We’ll then look at some problems that involve simultaneous linear congruences, such as the pirates puzzle above. Finally, we’ll extend our explorations to some quadratic congruences of the form .
We’ll start by looking in turn at three congruences:
For the first congruence we discover, after a little experimentation, that is a solution, because
Exploring a little further, we find that and are also solutions, as are any other numbers that are congruent to 4 (mod 6). These turn out to be the only solutions.
The second congruence has two solutions, and , or more generally any number that is congruent to 2 or 5 (mod 6).
The third congruence has no solutions.
To see why these different situations arise, let’s begin with the third congruence.
If , then the left-hand side is always even, and so can never equal a number of the form 3 (mod 6). So this congruence can have no solutions.
Turning our attention to the second congruence, we note that if , then , after cancelling throughout by 2. This has the single solution , which corresponds to or 5 (mod 6).
For the first congruence, , we find, after some experimentation, that multiplication by 5 gives the congruence —that is, . This is the only solution.
In general, we have the following rules for solving the congruence .
If , then there is a single solution for x (mod n).
If , and if d divides b, then there are d solutions (mod n), which correspond to the single solution of the congruence .
If gcd (a, n) doesn’t divide b, then the congruence has no solutions.
For the congruences above:
when , , and the only solution is ;
when , , so there are two solutions, and 5 (mod 6), which correspond to the single solution of the congruence ;
when , , which doesn’t divide 3, so there are no solutions.Simultaneous linear congruences
An ancient puzzle, posed in the 4th century by the Chinese mathematician Sunzi, asks:
There are an unknown number of things. If we count by threes, there’s a remainder of 2; if we count by fives, there’s a remainder of 3; if we count by sevens, there’s a remainder of 2. Find the number of things.
He answered this problem, together with many similar examples, in the Sunzi suan jing (Mathematical Classic of Master Sun), and over the next millennium it resurfaced in many lands and in many forms, such as the following:
I have some eggs. Arranged in rows of 3 there are 2 left over, in rows of 5 there are 3 left over, and in rows of 7 there are 2 left over. How many eggs have I altogether?
In either version, we seek a number x that simultaneously satisfies the congruences
We can answer Sunzi’s problem by first trawling through the numbers congruent to 2 (mod 7) until we reach a number that’s also congruent to 3 (mod 5): this gives
So is a solution of the last two congruences, and it also satisfies the first one. Other answers can then be found by adding multiples of , because 105 is congruent to 0 (mod 3), 0 (mod 5), and 0 (mod 7): for example, and are also solutions to Sunzi’s problem.
We were fortunate that a solution to the last two congruences also satisfies the first one, but this doesn’t usually happen. For example, let’s return to the pirates puzzle, where we seek a simultaneous solution to the congruences
To solve this puzzle we first trawl through the numbers congruent to 4 (mod 17) until we reach a solution to the second congruence:
We next trawl through the simultaneous solutions of the first two congruences, by adding each time, until we reach a solution of the third congruence:
So satisfies all three congruences and is the smallest solution of the pirates problem. Other solutions can then be obtained by adding multiples of .
It turns out that any collection of simultaneous congruences has a single solution, provided that the moduli are coprime in pairs: for example, in Sunzi’s problem, the moduli 3 and 5 are coprime, as are 3 and 7, and 5 and 7, and the same is true for the moduli in the pirates puzzle. A statement of what became known as the Chinese remainder theorem, in the case of three congruences, is as follows:
Chinese remainder theorem: Let n1, n2, and n3 be positive integers with
Then the linear congruences
have a simultaneous solution which is unique (mod N).
We conclude this section with another poser that leads to solving simultaneous linear congruences. A number n is self-replicating if its square n2 terminates in the digits of
