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

the sequence

a2m

+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

a2m

+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

22r

(where r ≥ 0), then

a2m

+1

is composite for infinitely many natural numbers m.

Proof. Fix an integer a 1 not of the form

22r

. Let M0 be an arbitrary

positive integer. We will show that

a2m

+ 1 is composite for some m ≥ M0.

Let Fj be a prime Fermat number not dividing

a(a2M0

− 1). Since a is

coprime to Fj, Fermat’s little theorem implies that

aFj −1

=

a22j

≡ 1 (mod Fj).

Since Fj

a2M0

− 1, we must have M0

2j.

So we can write

aFj −1

− 1 =

a22

j

− 1

=

(a2M0

−

1)(a2M0

+

1)(a2M0+1

+

1)(a2M0+2

+ 1) · · ·

(a22j

−1

+ 1).

Since Fj divides

aFj −1

− 1 but not

a2M0

− 1, it must be that Fj divides

a2m

+ 1 for some M0 ≤ m

2j.

We cannot have

a2m

+ 1 = Fj, since a is

not of the form

22r

, and so

a2m

+ 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

a2m

+ 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

abm

+ c

is composite for infinitely many m ∈ N, except possibly in the case when a

is even, c = 1, and b =

2k

for some k ≥ 1. If c is even, there are infinitely

many such m except possibly when a is odd and c = 2.