How many positive integers \(n\) are there such that \(n! + 1\) is composite?

Sunday, March 3, 2013

Please email your solutions to puzzles@cotpi.com.

### 3 comments

### Credit

This puzzle is taken from:

- Hobson, Nick. "Solution to puzzle 137: Factorial plus one equals prime power?" Nick's Mathematical Miscellany. 23 Jan. 2006. 3 Mar. 2013 <http://www.qbyte.org/puzzles/p120s.html>.

### Further reading

The following is a list of resources on related topics:

- Caldwell, Chris K. "A proof of Wilson's Theorem." The Prime Pages. University of Tennessee at Martin. 5 Aug. 2012 <http://primes.utm.edu/notes/proofs/Wilsons.html>.

## Tanny Libman solved this puzzle:

By Wilson's theorem, \((p - 1)! quiv -1 \pmod p\) for any prime \(p\). If \(n = p - 1\), then we get \(n! + 1 quiv 0 \pmod p\). Since \(n! + 1 \gt n + 1 = p\) for any \(n \gt 2\), we'll always have \(n! + 1 = pk\) for some integer \(k \gt 1\). That means \(n! + 1\) is composite. Since there are infinitely many primes \(p\), there are infinitely many values for \(p - 1 = n\) such that \(n! + 1\) is composite.

## Rino Raj solved this puzzle:

For any prime \(p\), we have \((p - 1)! \equiv -1 \pmod p\) by Wilson's theorem, so \(p \mid (p-1)! + 1\). Further for \(p \geq 5\), \((p - 1)! + 1 \gt p\), so \((p - 1)! + 1\) is composite. As the number of primes is infinite, the number of such composite cases is also infinite.

## Mark Brader solved this puzzle:

Infinitely many, or to be more specific, \(\aleph_0\).

Wilson's theorem states that \(p\) is prime if and only if \((p - 1)! + 1\) is divisible by \(p\). If \(x \gt 3\), then \((x - 1)! + 1 \gt x\). Therefore the desired property holds for all numbers \(n \gt 4\) where \(n - 1\) is prime, and there are \(\aleph_0\) of those.