Is either $n! + 1$ or $n! - 1$ not prime for all $n$?

Solution 1:

The OEIS entry on factorial primes currently states that this is an open problem:

Conjecture: 3 is the intersection of A002981 and A002982.

The two referenced sequences consist of the natural numbers $n$ such that $n!+1$ is prime, and the $n$ such that $n!-1$ is prime, respectively. Their intersection is exactly the numbers $n$ you are looking for, where both $n!+1$ and $n!-1$ are prime.

Solution 2:

The smallest prime factors of $n!^2 - 1$ for the first few values of $n$ seem to me to be bizarrely small but I only know how to "explain" some of them. Wilson's theorem gives, for a prime $p$, the following:

$$(p-1)! \equiv -1 \bmod p$$ $$(p-2)! \equiv 1 \bmod p$$ $$\left( \frac{p-1}{2} \right)! \equiv \pm 1 \bmod p, p \equiv 3 \bmod 4$$

(the last one is a nice exercise). More generally we have

$$(p-k)! \equiv (-1)^k (k-1)! \bmod p$$

which will explain one mystery a bit later. Now, applying the first three facts, we have

$$3! \equiv 1 \bmod 5, -1 \bmod 7$$ $$4! \equiv -1 \bmod 5$$ $$5! \equiv 1 \bmod 7, -1 \bmod 11$$ $$6! \equiv -1 \bmod 7$$

The first one I don't know how to explain is

$$7! \equiv -1 \bmod 71$$

but it's striking that $71 \equiv 1 \bmod 7$. Also we have

$$8! \equiv 1 \bmod 23, -1 \bmod 61$$

which I also don't know how to explain, but it's again striking that $23 \equiv -1 \bmod 8$. Then we have easy Wilson cases again,

$$9! \equiv 1 \bmod 11, -1 \bmod 19$$ $$10! \equiv -1 \bmod 11$$ $$11! \equiv 1 \bmod 13, 23$$ $$12! \equiv -1 \bmod 13$$

and then the fairly mysterious

$$13! \equiv -1 \bmod 83$$

(here we have $83 \equiv 5 \bmod 13$ which is a square root of $-1 \bmod 13$, what's up with that) and the somewhat more explainable

$$14! \equiv (23-9)! \equiv -8! \equiv -1 \bmod 23.$$

Next is a round of Wilson's theorem again:

$$15! \equiv 1 \bmod 17$$ $$16! \equiv -1 \bmod 17$$ $$17! \equiv 1 \bmod 19$$ $$18! \equiv -1 \bmod 19$$

and then

$$19! \equiv -1 \bmod 71$$

(recall that we saw above that $7! \equiv -1 \bmod 71$, and I didn't include it above but we also have $9! \equiv -1 \bmod 71$). Up until this point the smallest prime factor was at most $2$ digits which I personally think is wacky, but now I am defeated: for $n = 20$ the smallest prime factor is

$$20! \equiv 1 \bmod 124769$$

so whatever's been powering our luck it's run out. There are some other coincidences I don't know how to explain: for example, $61$ divides not only $8!+1$ but also $16!+1$ and $18!+1$, and $661$ divides not only $8!+1$ but also $17!+1$. Very strange.

Solution 3:

This is not a full answer, but some supporting material, explicitly requested in comments.

First, in Mathematica here is non-optimized code to show how to perform the posed search (for $n = 1000, \ldots 2000$) on a four-processor machine:

CloseKernels[]; 
LaunchKernels[4];
Parallelize[
 {t1 = 1000!;
  Do[t = t1 n;
   If[PrimeQ[t - 1], If[PrimeQ[t + 1], Print[t]]],
   {n, 1001, 1300}],
  t2 = 1300!;
  Do[t = t2 n;
   If[PrimeQ[t - 1], If[PrimeQ[t + 1], Print[t]]],
   {n, 1301, 1600}],
  t3 = 1600!;
  Do[t = t3 n;
   If[PrimeQ[t - 1], If[PrimeQ[t + 1], Print[t]]],
   {n, 1601, 1800}],
  t4 = 1800!;
  Do[t = t3 n;
   If[PrimeQ[t - 1], If[PrimeQ[t + 1], Print[t]]],
   {n, 1801, 2000}]
  }
 ]

In brief, there are four threads, each covering at a different range of $n$. (You don't want equal-sized ranges of $n$s, because the large $n$s require more compute time, of course.)

Now, here's a table of $n$ and the factors of $n!-1$ and $n!+1$.

Here's the Mathematica code... just change $20$ to $50$ or whatever you like.

TableForm[
 Table[{n, FactorInteger[n! - 1], FactorInteger[n! + 1]},
  {n, 1, 20}]
 ]

$$\left( \begin{array}{ccc} 1 & \left( \begin{array}{cc} 0 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 2 & 1 \\ \end{array} \right) \\ 2 & \left( \begin{array}{cc} 1 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 3 & 1 \\ \end{array} \right) \\ 3 & \left( \begin{array}{cc} 5 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 7 & 1 \\ \end{array} \right) \\ 4 & \left( \begin{array}{cc} 23 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 5 & 2 \\ \end{array} \right) \\ 5 & \left( \begin{array}{cc} 7 & 1 \\ 17 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 11 & 2 \\ \end{array} \right) \\ 6 & \left( \begin{array}{cc} 719 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 7 & 1 \\ 103 & 1 \\ \end{array} \right) \\ 7 & \left( \begin{array}{cc} 5039 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 71 & 2 \\ \end{array} \right) \\ 8 & \left( \begin{array}{cc} 23 & 1 \\ 1753 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 61 & 1 \\ 661 & 1 \\ \end{array} \right) \\ 9 & \left( \begin{array}{cc} 11 & 2 \\ 2999 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 19 & 1 \\ 71 & 1 \\ 269 & 1 \\ \end{array} \right) \\ 10 & \left( \begin{array}{cc} 29 & 1 \\ 125131 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 11 & 1 \\ 329891 & 1 \\ \end{array} \right) \\ 11 & \left( \begin{array}{cc} 13 & 1 \\ 17 & 1 \\ 23 & 1 \\ 7853 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 39916801 & 1 \\ \end{array} \right) \\ 12 & \left( \begin{array}{cc} 479001599 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 13 & 2 \\ 2834329 & 1 \\ \end{array} \right) \\ 13 & \left( \begin{array}{cc} 1733 & 1 \\ 3593203 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 83 & 1 \\ 75024347 & 1 \\ \end{array} \right) \\ 14 & \left( \begin{array}{cc} 87178291199 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 23 & 1 \\ 3790360487 & 1 \\ \end{array} \right) \\ 15 & \left( \begin{array}{cc} 17 & 1 \\ 31 & 2 \\ 53 & 1 \\ 1510259 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 59 & 1 \\ 479 & 1 \\ 46271341 & 1 \\ \end{array} \right) \\ 16 & \left( \begin{array}{cc} 3041 & 1 \\ 6880233439 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 17 & 1 \\ 61 & 1 \\ 137 & 1 \\ 139 & 1 \\ 1059511 & 1 \\ \end{array} \right) \\ 17 & \left( \begin{array}{cc} 19 & 1 \\ 73 & 1 \\ 256443711677 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 661 & 1 \\ 537913 & 1 \\ 1000357 & 1 \\ \end{array} \right) \\ 18 & \left( \begin{array}{cc} 59 & 1 \\ 226663 & 1 \\ 478749547 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 19 & 1 \\ 23 & 1 \\ 29 & 1 \\ 61 & 1 \\ 67 & 1 \\ 123610951 & 1 \\ \end{array} \right) \\ 19 & \left( \begin{array}{cc} 653 & 1 \\ 2383907 & 1 \\ 78143369 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 71 & 1 \\ 1713311273363831 & 1 \\ \end{array} \right) \\ 20 & \left( \begin{array}{cc} 124769 & 1 \\ 19499250680671 & 1 \\ \end{array} \right) & \left( \begin{array}{cc} 20639383 & 1 \\ 117876683047 & 1 \\ \end{array} \right) \\ \end{array} \right)$$