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

[SOLVED]

3 comments

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.

Credit

This puzzle is taken from:

Further reading

The following is a list of resources on related topics:

Post a comment

RSS