Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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..
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.
