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
