10. Primes and composites in other sequences 31

The reader should note that the Shapiro–Sparer paper contains several

other attractive results on composite numbers in various sequences.

We close this section by considering the sequence of shifted factorials

n! + 1. Here we can easily obtain infinitely many composite terms, since

Wilson’s theorem implies that (p − 1)! + 1 is composite for each p 3. The

following pretty theorem of Schinzel [Sch62b] generalizes this result:

Theorem 1.31. Let α be a positive rational number. Then there are infin-

itely many n for which α · n! + 1 is composite.

Lemma 1.32. Let p be a prime and let r and s be positive integers. Then

for 0 ≤ i ≤ p − 1, we have

p | si! +

(−1)i+1r

⇐⇒ p | r(p − 1 − i)! + s.

Proof. By Wilson’s theorem,

−1 ≡ (p − 1)! = (p − 1)(p − 2) · · · (p − i)(p − i − 1)!

≡

(−1)ii!(p

− 1 − i)! (mod p),

so that (p−1−i)!i! ≡

(−1)i+1

(mod p). Since p and (p−1−i)! are coprime,

p | si! +

(−1)i+1r

⇐⇒ p | s(p − 1 − i)!i! +

(−1)i+1r(p

− 1 − i)!

⇐⇒ p |

(−1)i+1s

+

(−1)i+1r(p

− 1 − i)!

⇐⇒ p | s + r(p − 1 − i)!.

Proof of Theorem 1.31. Write α = r/s, where r and s are relatively

prime positive integers. Assume l ∈ N and l ≥ r/2. Then

(4l)!α−1

is an

integer divisible by both 4 and r. Since 4 |

(4l)!α−1,

we can choose a prime

pl ≡ −1 (mod 4) with

pl |

(4l)!α−1

− 1.

Because r |

(4l)!α−1,

necessarily pl r. Since

(1.13) pl | r

(

(4l)!α−1

− 1

)

= s(4l)! − r,

we must have pl 4l. From Lemma 1.32 (with i = 4l) and (1.13), we find

that

(1.14) pl | r(pl − 4l − 1)! + s.

Since pl r, (1.14) implies that pl s, and so

pl | Nl := α(pl − 4l − 1)! + 1

whenever Nl is an integer. This happens for all large l: Indeed, from (1.14)

we have Nl ≥ pl/s ≥ 4l/s, so that Nl → ∞ with l, which is only possible if

pl − 4l − 1 → ∞ with l. But Nl is an integer whenever pl − 4l − 1 ≥ s.

Finally, notice that for large l, we cannot have pl = Nl, since pl ≡

−1 (mod 4) while Nl ≡ 1 (mod 4). Thus Nl is a composite integer of the