30 1. Elementary Prime Number Theory, I
It is now known that Fm is composite for 5 ≤ m ≤ 32, and (for the same
probabilistic reasons alluded to above) it is widely believed that Fm is com-
posite for every m ≥ 5. So much for intuition! Despite this widespread
belief, the following conjecture appears intractable:
Conjecture 1.28. The Fermat number Fm is composite for infinitely many
natural numbers m.
Similarly, for each even natural number a, one can look for primes in
+1. Again we believe that there should be at most finitely
many, but again the analogue of Conjecture 1.28 seems impossibly diﬃcult!
Indeed, there is no specific even number a for which we can prove that
+1 is composite infinitely often. This is a somewhat odd state of affairs
in view of the following amusing theorem of Schinzel [Sch63]:
Theorem 1.29. Suppose that infinitely many of the Fermat numbers Fj are
prime. If a 1 is an integer not of the form
(where r ≥ 0), then
is composite for infinitely many natural numbers m.
Proof. Fix an integer a 1 not of the form
. Let M0 be an arbitrary
positive integer. We will show that
+ 1 is composite for some m ≥ M0.
Let Fj be a prime Fermat number not dividing
− 1). Since a is
coprime to Fj, Fermat’s little theorem implies that
≡ 1 (mod Fj).
− 1, we must have M0
So we can write
− 1 =
+ 1) · · ·
Since Fj divides
− 1 but not
− 1, it must be that Fj divides
+ 1 for some M0 ≤ m
We cannot have
+ 1 = Fj, since a is
not of the form
, and so
+ 1 is composite.
In connection with Fermat-type numbers the following result of Shapiro
& Sparer [SS72] merits attention (cf. [Sha83, Theorem 5.1.5]). It shows
(in particular) that the doubly exponential sequences
+ 1 are unusually
diﬃcult to handle among sequences of the same general shape:
Theorem 1.30. Suppose a, b, and c are integers, and that a, b 1. If c
is odd, then
is composite for infinitely many m ∈ N, except possibly in the case when a
is even, c = 1, and b =
for some k ≥ 1. If c is even, there are infinitely
many such m except possibly when a is odd and c = 2.