10. Primes and composites in other sequences 29

10. Primes and composites in other sequences

We conclude by discussing the occurrence of primes in other sequences of

interest. Results in this area are rather thin on the ground, and so we content

ourselves with a smattering of problems and results meant to showcase our

collective ignorance.

One sequence that has received much attention is that of the Mersenne

numbers

2n

− 1. The occurrence of primes in this sequence has long been of

interest in view of Euclid’s result that if 2n − 1 is prime, then 2n−1(2n − 1)

is a perfect number. (Here a number is called perfect if it is the sum of

its proper divisors.) Since

2d

− 1 divides

2n

− 1 whenever d divides n, for

2n

− 1 to be prime it is necessary that n be prime. At first glance it appears

that

2p

− 1 is often prime; 7 of the first 10 primes p have this property.

However, the tide quickly turns: Of the 78498 primes p up to

106,

only 31

yield primes. As of February 2009, there are 46 known primes of the form

2p

− 1, the largest corresponding to p = 43112609. It is not clear from this

data whether or not we should expect infinitely many primes of this form,

but probabilistic considerations to be discussed in Chapter 3 suggest that

we should:

Conjecture 1.26. For infinitely many primes p, the number

2p−1

is prime.

Unfortunately, this conjecture seems far beyond reach. In fact, we know

disturbingly little about the numbers

2p

− 1; perhaps the most striking

illustration of this is that even the following modest conjecture remains

unproved:

Conjecture 1.27. For infinitely many primes p, the number

2p

− 1 is com-

posite.

We may also change the “−” sign to a “+” and consider primes of the

form

2n

+ 1. Since

2d

+ 1 divides

2n

+ 1 when n/d is odd, we see that

2n

+ 1

can be prime only if n is a power of 2. This leads us to consider the Fermat

numbers Fm =

22m

+ 1. The attentive reader will recall that these numbers

appeared already in Goldbach’s proof of Theorem 1.1. For m = 0, 1, 2, 3,

and 4, the numbers Fm are prime:

220

+1 = 3,

221

+1 = 5,

222

+1 = 17,

223

+1 = 257,

224

+1 = 65537.

Fermat was intuitively certain that Fm is prime for all m ≥ 0, and expressed

this belief in letters to his contemporaries; but in 1732 Euler discovered the

factorization

225

+ 1 = 641 · 6700417.