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.