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.
Previous Page Next Page