# Determine whether $712! + 1$ is a prime number or not

Let $n = 712! + 1$ If $n$ was a prime number then, by Wilson's theorem:

$(712!)! \equiv -1 \pmod{712}$

The double factorial makes it seriously more difficult...

But We can require:

$$712!! + 1 \equiv 0 \pmod{712}$$

$$712 = 2\cdot 356$$

Hence: $712!! = 2^{356} 356!$

Lets compute: $356! \pmod{712}$. Obviously:

$$356! = (356 \cdot 2) \cdot (355!/2) = 712 \cdot 355!/2$$

Then: $356! \pmod{712} \equiv 0$.

Now, $2^{356} \pmod{712}$

$2^{356} = 2^{6 + 350}$

Nevermind, what should I do?

• The Maple command isprime answers "false". – user64494 Feb 9 '15 at 14:55
• I think you mixed up $(712!)!$ with $712!!$. – mercio Feb 9 '15 at 15:05
• I don't have a better answer than "Well, you could try trial division" - and it happens that $719$ divides $712!+1$, so trial division is okay in this case. In general, such a method would require lots of luck... – Milo Brandt Feb 9 '15 at 15:33
• $(712!)! \equiv -1 \pmod{712}\iff 0\equiv -1\pmod {712}\iff 712\mid 1$ leads to an obvious contradiction, but the first congruence is actually $(712!)! \equiv -1 \pmod{712!+1}$. – user26486 Feb 9 '15 at 15:47
• Hint $\$ By Wilson factorial reflection, prime $\, p>7 \ \Rightarrow\ p\,\mid\, 1+(\color{#c00}7\!-\!1)!\,(p-\color{#c00}7)!\ \$ – Gone Feb 9 '15 at 18:11

Since $719$ is prime, by Wilson's theorem we have that $$718!\equiv 718\cdot 717\cdot 716\cdot 715\cdot 714\cdot 713\cdot 712!\equiv -1\pmod {719}$$

To prove that $719\mid 712!+1$, it is sufficient to prove that \begin{align}718\cdot 717\cdot 716\cdot 715\cdot 714\cdot 713&\equiv 1\pmod {719}\\\iff(-1)\cdot(-2)\cdot(-3)\cdot(-4)\cdot(-5)\cdot(-6)&\equiv 1\pmod {719}\\\iff 6!&\equiv 1\pmod {719}\\\iff 720&\equiv 1\pmod {719}\ \ \ \square \end{align}

• That is fine but you still need to know to look at $719$. – lhf Feb 9 '15 at 16:36
• @Ihf To be fair, I saw this at a recent olympiad a few months ago, and the official solution was exactly this. I honestly disagree it is at all difficult to think of this solution. Proving that $n!+1$ is prime for a large enough $n$ is really difficult, and so naturally you would expect an olympiad problem to ask to prove its compositeness. Naturally, $n!+1$ is not easily factorable in any way. The only natural way I can think of to proceed here is to use modular arithmetic to prove that a particular prime divides $712!+1$, and the only reasonable way to do this is Wilson's theorem. – user26486 Feb 9 '15 at 16:54
• @Ihf And now that you know it is Wilson's theorem you're going to use and there's no way you can factor anything here, you're going to start by checking primes close to $712$. – user26486 Feb 9 '15 at 16:58
• It is $\,k=6\,$ in Wilson factorial reflection:  prime $\, p>k \ \Rightarrow\ p\,\mid\, (-1)^k\!+k!\,(p\!-\!k\!-\!1)!\ \$ – Gone Feb 9 '15 at 18:17
• Still doesnt make sense. how does this possible help show $712! +1$ is not prime? – Lebes Feb 17 '15 at 13:27

No, $712!+1$ is not prime, see here in integer sequences. Further references are given there. The next factorial prime here is $872!+1$. See also the comments here, and this article by Caldwell and Gallot.

• How do you prove that? – Lebes Feb 9 '15 at 14:58
• Not necessarily a proof. But In general how would i determine if $n! + 1$ was prime or not? – Lebes Feb 9 '15 at 15:02
• Special primality tests for factorial primes, see here, or here. – Dietrich Burde Feb 9 '15 at 15:05
• @Lebes Find some primes $p_1,\ldots,p_k>n$ close to $n$ and then check using Wilson's theorem whether or not they divide $n!+1$. See my answer for an example. – user26486 Feb 9 '15 at 18:22