by Robin Wilson
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 the original number n: for example, 25 is self-replicating because , which terminates in 25. Are there any more?
The 1-digit self-replicating numbers are 0, 1, 5, and 6, because , , , and . These numbers all satisfy the congruence .
For 2-digit self-replicating numbers, n is self-replicating if . But if 100 divides , then so do 4 and 25, and we get the simultaneous congruences
It follows from the first of these congruences that or 1 (mod 4).
For the second congruence, we notice that 25 divides , and so either 5 divides both n and (which cannot happen) or 25 must divide n or . It follows that or 1 (mod 25). So we have four pairs of simultaneous linear congruences:
and , with solution which isn’t a 2-digit number;
and : this has the solution , which we saw earlier;
and : this has the solution , with ;
and , with solution which isn’t a 2-digit number.
So the only two 2-digit self-replicating numbers are and .
Likewise, for 3-digit self-replicating numbers, we have the congruence , from which we get the simultaneous congruences
These in turn lead to the simultaneous linear congruences or 1 (mod 8) and or 1 (mod 125), and on examining these in pairs, as above, we find that the only 3-digit self-replicating numbers are and 625, with and .
Squares and non-squares
We conclude this chapter by looking at some more quadratic congruences. Our explorations will lead us to one of the most important results in number theory, the law of quadratic reciprocity.
We’ll start with the congruence
We can solve this by multiplying by 4 and adding 9 to both sides, giving
Taking the square root now gives or , and these two linear congruences can then be solved to give and . These solutions are correct, because
It turns out that many quadratic congruences can likewise be rewritten in the form —here, , , and —and this leads us to investigate which numbers b are squares (mod n) and which ones are non-squares. We’ll now explore this question when n is an odd prime number.
Let’s first find the squares (mod p) when . Because is always a square, whatever the value of p, we’ll seek only non-zero squares.
When , the non-zero squares are and ,
so the only non-zero square (mod 3) is 1, and the only non-square is 2.
When , the non-zero squares are
so the non-zero squares (mod 5) are 1 and 4, and the non-squares are 2 and 3.
When , the non-zero squares are:
so the non-zero squares (mod 7) are 1, 2, and 4, and the non-squares are 3, 5, and 6.
When , the non-zero squares are:
so the non-zero squares (mod 11) are 1, 3, 4, 5, and 9, and the non-squares are 2, 6, 7, 8, and 10.
We notice that in each case the numbers of squares and non-squares are the same, and this is the case for all primes. The squares are often called quadratic residues (mod p) and the non-squares are called quadratic non-residues (mod p).
If we multiply two squares (mod p) together, then the product is also a square: this is because
We can likewise prove that
the product of any two non-squares (mod p) is a square,
and
the product of a square and a non-square (mod p) is a non-square.
For example, when ,
6 and 7 are both non-squares, and their product is a square;
5 is a square and 7 is a non-square, and their product is a non-square.
Given an odd prime number p, how can we decide whether a given number a is a square or a non-square (mod p)? For example, knowing that 2027 is a prime, is 1066 a square or a non-square (mod 2027)? We’ll answer this question later.
In 1798 Adrien-Marie Legendre introduced a useful notation that helps us when answering such questions. If p is an odd prime number and a is a number that’s not divisible by p, then his Legendre symbol (a / p) is defined by
for example, and , because 5 is a square and 6 and 7 are non-squares (mod 11). We note that, for any odd prime number p, and any number a that is not divisible by p,
for example, .
There are some useful rules that help us to find Legendre symbols. The first is:
If a and b are not divisible by p, and if , then .
For example, 42 is a square (mod 11), because , and so
The second rule restates the above remarks about multiplying squares and non-squares:
If a and b are not divisible by p, then .
For example, 42 is a square (mod 11), because
It can also be shown that, for any odd prime p,
These results conveniently tell us when −1 and 2 are squares (mod p). For example,
and , because and ;
and , because and .
Suppose next that we wish to decide whether 41 is a square (mod 23).
By the first rule we can write
So , and 41 is a square (mod 23).
Another way to deduce this is to spot that .
Suppose now that we wish to decide whether 42 is a square (mod 23)?
Here, , and so . But how can we decide whether 19 is a square (mod 23) without having to calculate all the squares (mod 23)?
To answer this, we’ll introduce the ‘law of quadratic reciprocity’, which provides a reciprocal relationship between the
squares (mod p) and the squares (mod q) when p and q are both odd primes. It was known to both Euler and Lagrange, but it was Gauss who presented no fewer than eight proofs of it—indeed, he became so excited by it that he called it his ‘Golden theorem’. There are now around two hundred proofs of the reciprocity law, which states:
For example,
We can now return to our problem of deciding whether 42 is a square (mod 23).
Above we saw that . But
So , and 42 is a non-square (mod 23).
We conclude this chapter by returning to our earlier problem of deciding whether 1066 is a square or a non-square (mod 2027). We can now answer this by applying the law of quadratic reciprocity several times to reduce the numbers involved. Because , we have
But , because . Also,
Finally,
Combining all of these results gives , and so 1066 is not a square (mod 2027).
In Chapter 6 we’ll continue our explorations into congruences with some fundamental results of Fermat and Euler and with some applications to cryptography and to the shuffling of cards and the colouring of necklaces.
Chapter 5
More triangles and squares
There are many intriguing problems that can be expressed in terms of equations requiring whole-number solutions: such equations are called Diophantine equations. They are named after Diophantus of Alexandria who, as we mentioned in Chapter 1, wrote a classic text called Arithmetica which contained many questions with such solutions. In this chapter we’ll present a number of Diophantine problems, ranging from finding right-angled triangles with integer sides to writing numbers as the sum of squares and higher powers, and we’ll conclude with a brief account of one of number theory’s most celebrated achievements—the proof of Fermat’s so-called ‘last theorem’.
Linear Diophantine equations
As an example of a Diophantine equation, we’ll consider the equation
If x and y can take any values, then there are infinitely many solutions—choose any number x, and calculate : for example, if , then .
If we now require x and y to be integers, then there are still infinitely many solutions—reducing the equation (mod 3) gives , so and the solutions become , , where k is an integer: for example, taking gives the solution , .
But if we further require x and y to be positive integers, then there are only two solutions:
These solutions are illustrated in Figure 25.
25. Some solutions of the Diophantine equation .
In general, it can be shown that:
If a, b, and c are given integers, then the linear equation
has a solution in integers if and only if gcd (a, b) divides c.
For the example above, we had , , and , which divides 13.
Moreover:
If , and if we can spot a particular solution, , , then every solution can be written in the form
For the example above, and , and , and so the solutions all have the form
as we saw earlier.
Another type of linear Diophantine problem is the following, adapted from one of Leonardo Fibonacci in 1202:
If I can buy partridges for 3 cents, pigeons for 2 cents, and 2 sparrows for a cent, and if I spend 30 cents on buying 30 birds, how many birds of each kind must I buy?
Because the birds are indivisible, we seek whole-number solutions. Further, we’ll assume that I buy at least one of each type of bird, so we seek positive solutions. If I buy a partridges, b pigeons, and c sparrows, then we can write down two equations:
At first sight it may seem that, with three unknowns and only two equations, we cannot answer the question. But we have a further piece of information: a, b, and c are all positive integers. Let’s proceed:
Multiplying the second equation by 2 gives
and then on subtracting the first equation from this to eliminate c, we get
So b is divisible by 5, and cannot be 10 (because a would then be 0). So , giving and (from the first equation) .So I should buy 3 partridges, 5 pigeons, and 22 sparrows.
Right-angled triangles
In Chapter 1 we saw that the sides a, b, and c of a right-angled triangle satisfy the Pythagorean theorem,
and we gave two examples of right-angled triangles with integer sides:
We call (a, b, c) a Pythagorean triple if and a, b, and c are positive integers, so (3, 4, 5) and (5, 12, 13) are Pythagorean triples. Our aim is to find all such triples.
We first note that if (a, b, c) is a Pythagorean triple, with , then so is any multiple (ka, kb, kc), where k is a positive integer, because
for example, (30, 40, 50) is also a Pythagorean triple. Geometrically, multiples of a Pythagorean triple correspond to scalings of the right-angled triangle.
Such scalings are not very interesting, and so we shall mainly consider triples in which the sides have no common factor k, other than 1. We call these primitive triples: for example, (3, 4, 5) and (5, 12, 13) are both primitive triples. Can we find a formula for generating all primitive triples?
We first note that if (a, b, c) is a primitive triple, then any two of the numbers a, b, and c must be coprime, for if (for example) a and b have a common factor that’s greater than 1, then they must have a common prime factor p. It follows that p must divide , which equals c2, and so p (being prime) also divides c. This contradicts the fact that a, b, and c have no common factor. We can therefore assume that
But we can say more. If (a, b, c) is a primitive triple, then a and b cannot both be even, as we’ve just seen. Can they both be odd? As we saw in Chapter 2, every square has the form 4n or , and so if a and b are both odd, then a2 and b2 must have the form , and c2 must have the form , which is impossible. So one of a and b must be even and the other must be odd, and c2, and hence c, must also be odd. For definiteness, we’ll always take a to be odd and b to be even.
Now, because a and c are both odd, their sum and difference are both even and we can write and , for some integers u and v, with . So and .
Also, b is even and , and so
What can we say about u and v? If , where , then d divides and , and so divides both c and a, which cannot happen. So u and v are coprime. Also, because uv is a square and u and v are coprime, u and v must separately be squares, and so we can write and , for some integers x and y with . So
It can be checked that one of the numbers x and y is odd and the other is even, and that they are coprime. Tying all this together, we have our desired formula for primitive triples:
Primitive Pythagorean triples: If (a, b, c) is a primitive Pythagorean triple, then
where x and y are coprime integers, one odd and the other even, with .
For example, if and , then , , and , giving the triple (3, 4, 5). Likewise, if and , then , , and , giving the triple (5, 12, 13).
We can use this recipe to draw up a table of primitive Pythagorean triples, by listing all pairs of coprime integers x and y with one odd and the other even and , and calculating the corresponding values of a, b, and c. Table 4 lists all the primitive triples with no numbers exceeding 100. By extending this table as far as necessary, and then taking multiples, we can generate all the right-angled triangles with whole number sides.
Table 4. Primitive Pythagorean triples
We can also use our formula for primitive triples to answer such questions as:
How many primitive triples include the number 60?
Because 60 is even, we have , and so . Remembering that and that x and y are coprime with one of them even and the other odd, we find the following four possibilities:
A similar question is:
How many right-angled triangles with whole-number sides have a side of length 29?
Because 29 is prime, the lengths of the sides must form a primitive triple, so either
In the former case, and , and the triple is (21, 20, 29).
In the latter case, , so and . So and , and the triple is (29, 420, 421).
Sums of squares
Having just investigated th
e equation , we may ask a more general question that can be traced back to Diophantus:
Which numbers can be written as the sum of two perfect squares?
The first few examples are:
The numbers up to 20 that cannot be written as the sum of two squares are 3, 6, 7, 11, 12, 14, 15, and 19. Can we deduce a general pattern from this?
The first thing to remember is that any square has the form 4n or , and so the sum of two squares must have the form 4n, , or . So any number of the form cannot be a sum of two squares, and this rules out 3, 7, 11, 15, and 19. We also note that 6, 12, and 14, which are multiples of the forbidden numbers 3 and 7, cannot be written as the sum of two squares, whereas 9 and 18, which are multiples of 32, can be so written. By using these observations as guidelines, it turns out that we can completely describe which numbers can be written as the sum of two squares. The following result was stated by Fermat, and proved by Legendre in 1798:
Sum of two squares: A number can be written as the sum of two squares if and only if every prime factor that is congruent to 3 (mod 4) occurs to an even power.
For example, is the sum of two squares because 3 occurs to an even power, whereas and cannot be the sum of two squares because 3 occurs to an odd power in each case.
A useful result is that if m and n can be written as the sum of two squares, then so can their product mn. This is because, for and , a little algebra confirms the multiplication rule: