Tag Archives: prime numbers

My Favorite Number

A few weeks ago, one of my friends asked me the following question:

As a mathematician, what is your favorite number?

My first response was tongue-in-cheek.  I said that I would probably pick 2 or 3.  After all, I rarely work with large numbers in any of my mathematics classes.  Furthermore, as this blog post on Gödel’s Lost Letter shows, there’s a lot of mathematically interesting things about two and three. However, after some more talking and thinking, I remembered a story that I had heard in my number theory class about a particularly special large number,

M_{67} = 2^{67} - 1

M_{67} is a special type of number called a Mersenne number, which are the numbers that can be expressed in the form 2^n - 1 for an integer n.  In particular, if a Mersenne number is prime, we say it is a Mersenne prime.  A000668 is the OEIS entry for the sequence of Mersenne primes, and according to the Great Internet Mersenne Primes Search (GIMPS), there are currently 48 known Mersenne primes.  It is conjectured that there are an infinite number of Mersenne primes.

Why are we interested in figuring out when Mersenne numbers are prime?  We will soon see that it is (relatively) easy to generate a list of potential Mersenne primes.  Furthermore, by the Lucas-Lehmer primality test, there is an extremely simple algorithm for determining whether or not a Mersenne number is prime.  These two facts combined means that finding Mersenne primes is the quickest way to finding the largest prime numbers.  Indeed, the current top ten largest known primes are all Mersenne primes.

Theorem.  If M_n = 2^n - 1 is prime, then n must be prime.

We prove the contrapositive statement: If n is composite, then M_n = 2^n - 1 is composite.  Assuming n is composite, we can write n = ab, with a, b > 1.  We then claim that (2^a - 1) properly divides (2^{ab} - 1).  This is clear, since (2^a - 1) > 1, and

2^{ab} - 1 = (2^a - 1)(2^{(b-1)a} + 2^{(b-2)a} + \dots + 2^a + 1)

Therefore, Mersenne primes must be of the form M_p = 2^p-1, where p is prime.  Since we can find primes up to 9 digits through other means without too much effort, we now have a list of potential Mersenne primes, with digits numbering in the millions.

However, notice it is not the case that if p is prime, then M_p = 2^p-1 is prime.  In fact, for p = 11, we have that 2^{11} - 1 = 2047 = 23*89.  So, back in the 17th century, Marin Mersenne, for whom these numbers are named after, came up with the following list of primes p for which he claimed M_p was prime:

Claim (Mersenne). For n =2 , 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257, M_n is prime.  M_n is composite for all other n < 257.

At the time, his claim could not have been verified or proven, and it turns out that his claim was incorrect:  missing from his list were M_{61}, M_{89}, and M_{107}, which were shown to be prime.  Furthermore, M_{67} and M_{257} were shown to be composite.  This sets the stage for the following anecdote:

In 1903, Frank Cole was to give a talk.  Without a word, he went up to the blackboard, and began to raise 2 to the 67th power, and then subtracted 1.  Then, on the other side of the board, he multiplied 193,707,721 by 761,838,257,287, and got the same number.  He then returned to seat with applause, not having said a single word.

And that’s the story of my favorite number.  There are a bunch of other interesting large numbers in mathematics, as these posts on mathoverflow, math.stackeschange, and reddit indicate.  What’s your favorite number?