5.4: Fermet and Mersenne Primes

Through the ages, back to early antiquity, people have been fascinated by numbers, such as \(6\), that are the sum of their divisors other than itself, to wit: \(6 = 1+2+3\). Mersenne and Fermat primes, primes of the form \(2^{k} \pm 1\), have attracted centuries of attention. Note that if \(p\) is a prime other than \(2\), then \(p^{k} \pm 1\) is divisible by \(2\) and therefore not a prime.

Definition 5.11

1. The Mersenne primes are \(M_{k} = 2^{k}-1\). A Mersenne prime is a Mersenne number that is also prime.
2. The Fermat primes are \(F_{k} = 2^{2^k}-1\). A Fermat prime is a Fermat number that is also prime. The number \(n \in \mathbb{N}\) is called perfect, if \(\sigma (n) = 2n\)

Lemma 5.12

1. If \(ad = k\), then \(2^{d}-1 | 2^{k}-1\).
2. If \(ad = k\) and \(a\) is odd, then \(2^{d}+1 | 2^{k}+1\).

Proof

We only prove (2). The other statement can be proved similarly. So suppose that \(a\) is odd, then

\[2^{d} = _{2^{d}+1} -1 \Rightarrow 2^{ad} = _{2^{d}+1} (-1)^{a} = _{2^{d}+1} -1 \Rightarrow 2^{ad}+1 = _{2^{d}+1} 0 \nonumber\]

which proves the statement. Notice that this includes the case where \(d=1\). In that case, we have \(3 | 2^{a}+1\) (whenever \(a\) odd).

A proof using the geometic series can be found in exercise 1.14. This lemma immediately implies the following.

Corollary 5.13

If \(2^{k}-1\) is prime, then \(k\) is prime.

If \(2^{k}+1\) is prime, then \(k=2^r\).

So, candidates of Mersenne primes are the numbers \(2^{p}-1\) where \(p\) is prime. This works for \(p \in \{0, 1, \cdots, 10\}\), but \(2^{11}-1\) is the monkey-wrench.

It is equal to \(23 \cdot 89\) and thus is composite. After that, the Mersenne primes become increasingly sparse. Among the first approximately \(2.3\) million primes, only \(45\) give Mersenne primes. As of this writing (2017), it is not known whether there are infinitely many Mersenne primes. In 2016, a very large Mersenne prime was discovered: \(2^{74,207,281}-1\). Mersenne primes are used in pseudo-random number generators.

Turing to primes of the form \(2^{k}+1\), the only candidates are \(F_{r} = 2^{2^{r}}+1\). Fermat himself noted that \(F_{r}\) is prime for \(0 \le r \le 4\), and he conjectured that all these numbers were primes. Again, Fermat did not quite get it right! It turns out that the 5-th Fermat number, \(2^{32}+1\), is divisible by \(641\) (see exercise 5.11). In fact, as of this writing in 2017, there are no other known Fermat primes among the first \(297\) 297 fermat numbers! Fermat primes are also used in pseudorandom number generators.

Lemma 5.14

If \(2^k-1\) is prime, then \(k>1\) and \(2^{k-1} (2^{k}-1)\) is perfect.

Proof

If \(2^{k}-1\) is prime, then it must be at least \(2\), and so \(k>1\). Let \(n = 2^{k-1} (2^{k}-1)\). Since \(\sigma\) is multiplicative and \(2^{k}-1\) is prime, we can compute (using Theorem 4.5):

\[\sigma (n) = \sigma (2^{k-1}) \sigma (2^{k}-1) = (\sum_{i=0}^{k-1} 2^i) 2^k = (2^{k}-1) 2^{k} = 2n \nonumber\]

which proves the lemma.

Theorem 5.15 (Euler's Theorem)

Suppose \(n\) is even. Then \(n\) is perfect if and only if \(n\) is of the form \(2^{k-1} (2^{k}-1)\) where \(2^{k}-1\) is prime.

Proof

One direction follows from the previous lemma. We only need to prove that if an even number \(n = _{q} 2^{k-1}\) where \(k \ge 2\), is perfectm then it is of the form stipulated.

Since \(n\) is even, we may assume \(n = _{q} 2^{k-1}\) where \(k \ge 2\) and \(2 \nmid q\). Using multiplicativity of \(\sigma\) and the fact that \(\sigma (n) = 2n\):

\[\sigma (n) = \sigma (q) (2^{k}-1) = _{q} 2^{k} \nonumber\]

Thus

\[(2^{k}-1) \sigma (q) - 2^{k} q = 0 \nonumber\]

Since \(2^{k}-(2^{k}-1) = 1\), we know by Bezout that \(\gcd ((2^{k}-1, 2^{k}) = 1\). Thus Propostion 3.5 implies that the general solution of the above equation is:

\[\begin{array} {ccc} {q=(2^{k}-1)t}&{\mbox{and}}&{\sigma (q) = 2^{k} t} \end{array} \nonumber\]

where \(t>0\), because we know that \(q>0\)

Assume first that \(t>1\). The form of \(q\), namely \(q = (2^{k}-1)t\), allow us to identify at least four distinct divisors of \(q\). This gives that

\[\sigma (q) \ge 1+t+(2^{k}-1)+(2^{k}-1)t = 2^{k}(t+1) \nonumber\]

This contradicts equation 5.2, and so \(t=1\).

Now use equation 5.2 again (with \(t = 1\)) to get that \(n = _{q}2^{k-1} = (2^{k}-1) 2^{k-1}\) has the required form. Futhermore, the same equation says that \(\sigma (q) = \sigma (2^{k}-1) = 2^k\) which proves that \(2^{k}-1\) is prime.

It is unknown at the date of this writing whether any odd perfect numbers exist.