7
$\begingroup$

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..

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.