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 5More 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,
