Number Theory: A Very Short Introduction
Page 6
Is the next Fermat number prime? This number is
Euler showed that any prime factors of must be of the form , for some integer k. Unfortunately, he could find no such prime number that divides , and he eventually gave up his search. But it turns out that is indeed composite, with 274,177 as its smallest prime factor, so it’s not surprising that Euler missed it. In fact,
Worse was to come: the next twenty-six Fermat numbers were also found to be composite. Indeed, no-one has ever found another Fermat number that’s prime, and so Fermat’s conjecture has turned out to be a rather unfortunate one.
A geometrical digression
Fermat primes turn up in unexpected places. A celebrated example from geometry arises in the construction of regular polygons—those polygons whose sides all have the same length and whose angles are all the same, such as an equilateral triangle, a square, or a regular pentagon (see Figure 20).
20. Some regular polygons.
The Ancient Greeks were interested in the construction of geometrical figures using only a ruler (for drawing straight lines) and compasses (for drawing circles); the ruler is assumed to be unmarked and no measuring is allowed. Indeed, the very first proposition in Euclid’s Elements, Book I, includes the construction of an equilateral triangle. Briefly it goes as follows (see Figure 21):
21. Constructing an equilateral triangle.
Given a line segment AB, use the compasses to draw the circle with centre A and radius AB, and the circle with centre B and radius BA.
These circles intersect at the point C: draw the lines AC and BC.
Then ABC is an equilateral triangle.
Euclid also showed how to construct squares and regular pentagons, and in Book IV he combined the constructions for triangles and pentagons to produce a regular polygon with sides. He also explained how to construct a regular polygon with 2n sides from one with n sides, by joining the centre of the surrounding circle to the midpoints of its sides (see Figure 22 for the case ).
22. Doubling the number of sides of a regular polygon.
It follows that:
from an equilateral triangle (with 3 sides), we can construct regular polygons with 6, 12, 24, … sides,
from a square (with 4 sides), we can construct regular polygons with 8, 16, 32, … sides,
from a regular pentagon (with 5 sides), we can construct regular polygons with 10, 20, 40, … sides.
So we can already construct regular polygons with 3, 4, 5, 6, 8, 10, 12, 15, and 16 sides.
But no-one has been able to construct regular polygons with 7, 9, 11, 13, or 14 sides, and this leads to the following question:
Which regular polygons can be constructed with an unmarked ruler and compasses?
The breakthrough was provided by the 18-year-old Carl Friedrich Gauss, who discovered a ruler-and-compasses method for constructing a regular 17-sided polygon. He then gave the following answer:
A regular polygon with n sides can be constructed if and only if n is a power of 2 multiplied by unequal Fermat primes.
It follows that one can construct regular polygons with
but not with
The following list gives the number of sides (up to 100) of regular polygons that can be constructed by an unmarked ruler and compasses:
It seems remarkable that Fermat primes arise in such a geometrical problem.
Two weird results
We conclude this chapter with two unexpected and rather bizarre results concerning primes.
The first of these is due to W. H. Mills who proved the following startling result in 1947:
There is a number x, with the property that, if we raise it to the powers 3, 9, 27, 81, … (the powers of 3) and then ignore the fractional part, we always get a prime number.
The smallest such number x, sometimes called Mills’ constant, is approximately equal to 1.30637788: for example,
Our second bizarre result involves the idea of a polynomial. This is an expression obtained by adding and subtracting multiples of powers of the variables a, b, c, etc.: for example,
In 1976 four mathematicians (J. Jones, D. Sato, H. Wada, and D. Wiens) discovered a somewhat horrendous polynomial in twenty-six variables (a, b, c, …, and z), with the following remarkable properties:
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 4
Congruences, 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 cop
rime: 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 1 (mod 9), and so
The method of ‘Casting out nines’ works because every number is congruent to its digital root (mod 9).
Testing for Mersenne primes
In Chapter 3 we saw that some Mersenne numbers (such as ) are prime, whereas others (such as ) are not. A method for testing whether a given Mersenne number is prime was discovered by Edouard Lucas in 1876 and refined in the 1930s by D. H. Lehmer:
The Lucas–Lehmer test. Let , where p is prime, and consider the sequence of numbers s0, s1, s2, s3, … in which and each successive number is defined by
Then Mp is prime if and only if the number sp−2 is congruent to 0 (mod Mp).
For example, if and , then we have
and , which is congruent to 0 (mod 127), so 127 is prime.
But, if and , then we have, after some calculation,
and , which is not congruent to 0 (mod 2047), so 2047 isn’t prime.
Congruences and the calendar
The seven days of the week cycle around like the hours on a clock (see Figure 24).
24. A 7-day clock.
If it’s now Thursday, then in four days it will be Monday.
If it’s now Saturday, then in three days it will be Tuesday.
The analogy is more obvious if we number the days of the week and work (mod 7):
The two statements above then become and .
We’ll use this analogy to answer various questions about the calendar: for example,
On which day of the week will 25 December 2099 fall?
In which years in the 21st century does February have five Sundays?
To simplify matters, we’ll concentrate mainly on dates in the 21st century.
The Gregorian calendar, introduced by Pope Gregory XIII in 1582, has been in use in the UK and its former colonies since 1752. In this calendar a regular year has 365 days and a leap year has an extra ‘leap day’ on 29 February. The leap years are those that are divisible by 4, except for the century years that are not also divisible by 400: so 2000 and 2400 are leap years, but 1900 and 2100 are not.
Because and , the day of the week on which any particular date falls advances by 1 each year, or by 2 when a leap day intervenes: for example, 1 January fell on a Monday in 2001, on a Tuesday in 2002, on a Wednesday in 2003, on a Thursday in 2004, and on a Saturday in 2005.
It’s useful to note that the days of the calendar repeat every 28 years in which no century year intervenes: this is because the number of days (ordinary days and leap days) is
which is divisible by 7. If we wish to take account of the century years, we can likewise check that the days of the calendar repeat every 400 years.
How can we calculate the day of the week on which a given date falls? Several puzzlers have discovered clever methods for doing so, including one by Gauss and a modern one called ‘Doomsday’ devised by the English mathematician John Conway. Here we present a method invented by the Oxford mathematician Charles L. Dodgson, better known as Lewis Carroll, the author of Alice’s Adventures in Wonderland. He published it under his pen-name in March 1887, and claimed to be able to carry out all the mental calculations in about 20 seconds.
Carroll’s method involves calculating four numbers—the century, year, month, and day numbers—and finding their sum (mod 7). We’ll illustrate it by calculating the day of the week on which 25 December 2099 will fall.
Century number. Divide the first two digits of the year by 4, subtract the remainder from 3, and multiply the result by 2.
So for the year 2099, we divide 20 by 4, giving a remainder of 0; subtracting this from 3 gives 3, and multiplying this by 2 gives the century number 6.
Year number. Divide the last two digits of the year by 12, and add the quotient, the remainder, and the number of times that 4 divides into the remainder.
So for the year 2099, we divide 99 by 12, giving a quotient of 8 and a remainder of 3; 4 divides this remainder no times, so the year number is
Month number. Carroll’s method for finding the month number was somewhat complicated, so we omit it. It yields the following table:
So for 25 December, the month number is 5.
Day number: this is simply the day of the month.
So for 25 December, the day number is 25.
Finally, the total of the four numbers then must be reduced by 1 if the date is in January or February of a leap year.
So for 25 December 2099, which is not in a leap year, adding the four numbers gives
so it will fall on a Friday.
We can now return to the following question that we asked earlier:
In which years in the 21st century does February have five Sundays?
For this to happen, the year must be a leap year, and the five Sundays must be 1, 8, 15, 22, and 29 February, so we need only to find out when 1 February is a Sunday. Now we know that 1 January 2001 was on a Monday, and that January has 31 ≡ 3 (mod 7) days, so that 1 February 2001 was on a Thursday. It follows that 1 February was on a Friday in 2002, on a Saturday in 2003, and on a Sunday in 2004. So February 2004 had five Sundays. Because the cycle of days repeats every 28 years, February also has five Sundays in the leap years 2032, 2060, and 2088.
Solving linear congruences
An ancient Chinese puzzle concerns a band of pirates and a hoard of gold coins:
A band of 17 pirates stole a sack of gold coins.
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 ;