If you substitute any integers you wish for all of the twenty-six variables, and if the result you get is a positive number, then it must be a prime number.
Moreover, every prime number can be obtained in this way, by making a suitable choice of the integers a, b, c, …, and z.
Their polynomial is
where
This polynomial can take a positive value only if all the squared terms, A2, B2, …, and N2 are 0, and so to discover prime values we need to solve fourteen simultaneous equations. Surprisingly, specific integers a, b, c, …, and z have never been found that give the prime number 2—but it’s still possible to prove that every prime number can be obtained in this way!
We’ll continue with our explorations of prime numbers in Chapter 7. But first, we’ll investigate a different type of arithmetic.
Chapter 4Congruences, clocks, and calendars
In 1801, in his revolutionary text Disquisitionae Arithmeticae, Gauss introduced the idea of ‘congruence’, a generalized form of equality that’s sometimes popularized as ‘clock arithmetic’. But its origins are much older than this, and in this chapter we’ll meet the ‘Chinese remainder theorem’, which can be traced back to Ancient China and yet has widespread applications throughout mathematics today. Further applications of congruences include testing for Mersenne primes and finding the day of the week on which a given date falls, and the chapter ends with Gauss’s celebrated law of quadratic reciprocity.
Clock arithmetic
Imagine a clock face (see Figure 23).
23. A 12-hour clock.
If it’s now 9 o’clock, then in 6 hours it will be 3 o’clock: we’ll write this as
Here, ‘mod 12’ means that we’re using a 12-hour clock, so that 15 (the sum of 9 and 6) is replaced by 3, and we write ‘≡’ instead of ‘=’ because it’s a different form of equality.
Similarly, if it’s now 10 o’clock, then in 7 hours it will be 5 o’clock, and we write this as
where 17 (the sum of 10 and 7) is replaced by 5. It turns out to be convenient to replace 12 by 0, so that if it’s 8 o’clock now, then in 4 hours it will be 0 o’clock, and we write this as
This type of calculation is called clock arithmetic: if we add the hours and get a number that’s 12 or larger, then we subtract 12 before giving the answer: the answer we give is then the remainder after we’ve divided the sum by 12, and is one of the numbers from 0 to 11.
In general, given any number n, greater than 1, we say that two integers a and b are congruent mod n if a and b leave the same remainder when divided by n, and we write
For example, as we’ve seen,
The abbreviation ‘mod’ is short for modulo, and the official name for clock arithmetic is modular arithmetic.
It follows from the definition that whenever the difference is divisible by n: for example,
Since the only remainders when we divide by n can be 0, 1, 2, …, or , every integer is congruent (mod n) to one of these: for example,
We can also carry out arithmetic on congruences, provided that we stick to the same modulus. For example, given the congruences and ,
we can add them to give , which we can rewrite as ;
we can subtract them to give , or ;
we can multiply them to give , or .
In general, if and , then
We can also add, subtract, or multiply a congruence by a constant integer: for example, starting with we can add 2, subtract 2, or multiply by 2, to give
In general, if and k is a constant, then
But we must be careful with division: for example, if we try to divide the congruence by 3, we get , which is false. In general, we can divide congruences mod n by a constant k only when n and k are coprime: for example, we can divide the congruence by 5 to give , because 5 and 7 are coprime. The general rule is:
If and if , then .
But if k and n are not coprime, then we have to change the modulus:
If and if , then .
Several results from Chapter 2 can be conveniently stated in terms of congruences.
For example:
Every square has the form 4n or , for some integer n
can be restated as
Every square is congruent to 0 or 1 (mod 4),
and other results on squares and cubes can be rewritten as
The square of every odd number is congruent to 1 (mod 8),
Every cube is congruent to 0, 1, or 8 (mod 9).
We can also revisit our earlier results on the divisibility of the integer
by various small numbers. For example:
Divisibility by 10: n is divisible by 10 if and only if its last digit is 0.
By the congruence rules, (mod 10), which is congruent to 0 (mod 10) when a0 is 0.
Divisibility by 4: n is divisible by 4 if and only if n ends in 00, 04, 08, …, or 96:
Here, , which is congruent to 0 (mod 4) when the two-digit number is 00, 04, …, or 96.
Divisibility by 9: n is divisible by 9 if and only if the sum of its digits is divisible by 9:
Here, the powers of 10 are all congruent to
