Solution to puzzle 120: Factorial plus one

Let n be a positive integer. Prove that n! + 1 is composite for infinitely many values of n.

We use Wilson's Theorem, which states that (p − 1)! −1 (modulo p) if, and only if, p is a prime number.
Hence, for any prime p, (p − 1)! + 1 is divisible by p.
For all p > 3, we also have (p − 1)! + 1 > p, so that (p − 1)! + 1 is composite.
Hence, for any n of the form p − 1, where p is a prime greater than 3, n! + 1 is composite.

The result now follows immediately, as there are infinitely many prime numbers.

Remarks

To prove that there are infinitely many prime numbers, we show that, given any finite (but non-empty) set of primes, S, we can generate an additional prime not in S. This implies that there is no upper limit on the cardinality of S; that is, there are infinitely many primes.

The key step in the algorithm is to take the product of all the primes in S, and add one. The resulting number, N, is not divisible by any of the primes in S, because dividing by any of these would leave a remainder of one. Therefore N must either be prime itself, or be divisible by some other prime that is not in S. Either way, we have generated at least one additional prime that is not in S.

We may now add to S all the prime factors of N, and begin another iteration of the algorithm. In this way, given any integer M, we can generate S with cardinality greater than M. This explicitly shows how to produce infinitely many primes.

The table below shows the first few iterations of this algorithm, beginning with S = {2}. See references 3 and 4, below, for further details.

Iterative generation of additional primes
S	Product of elements of S, plus one
{2}	2 + 1 = 3
{2, 3}	2×3 + 1 = 7
{2, 3, 7}	2×3×7 + 1 = 43
{2, 3, 7, 43}	2×3×7×43 + 1 = 1807 = 13×139
{2, 3, 7, 43, 13, 139}	2×3×7×43×13×139 + 1 = 3263443
{2, 3, 7, 43, 13, 139, 3263443}	2×3×7×43×13×139×3263443 + 1 = 10650056950807 = 547×607×1033×31051

Whether n! + 1 is prime for infinitely many values of n is an unsolved problem.

Solution to puzzle 120: Factorial plus one

Remarks

Further reading