# Proving $11! + 1$ is prime

Prove that:

$$11! + 1$$ is a prime number. Without computing the number (or factorial).

Obviously, from Wilson's theorem, a number $n$ is prime if,

$$(n-1)! + 1 \equiv 0 \pmod{n}$$

Since $n = 11! + 1 \in \mathbb{N}$, it is prime iff

$$(11!)! + 1 \equiv 0 \pmod{11! + 1}$$

I have a problem here, how do I use Wilson's theorem with factorials?

For a beginning,

Multiples of 11:

$$11, 22$$

$11! = 11*10*9...2*1 = 22*10!$

Next,

$$(11!)! = (22*10!)!$$

I need help at this point..

• shouldn't your third equation be $(11!)!+1 \equiv 0 \mod (11!+1)$? Feb 17, 2015 at 13:16
• @MichaelStocker, darn; yes. Feb 17, 2015 at 13:16
• Also $11! = 11\cdot 10!$ not $22\cdot 10!$. Feb 17, 2015 at 13:17
• You have written 11!=11*10*9*...*2*1=22*10!. here this is wrong Feb 17, 2015 at 13:18
• You have not yet edited your question. Kindly write 22*10!/2 in place of 22*10!. Feb 17, 2015 at 14:01

## 1 Answer

It can be shown to be prime using the Pratt certificate $g = 26$.

Specifically $p = 11!+1$ is prime if (A) $g^{11!} = 1 \pmod p$ and (B) $g^{11!/q} \not= 1 \pmod p$ for each $q$ in $2,3,5,7,11$.

We would expect both these facts to hold for any prime p by Fermats little theorem and existence of primitive roots. Condition (A) is easily verified.

With some computation it is found that $13$ and $26$ are the first two numbers $g$ that satisfy (B) with $q=2$, but $13$ is quickly ruled out as $13^{11!/3} = 1 \pmod p$. Condition (B) can be verified quickly with $g=26$ for all $q$ proving that $p$ is prime.