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

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ shouldn't your third equation be $(11!)!+1 \equiv 0 \mod (11!+1)$? $\endgroup$ – Michael Stocker Feb 17 '15 at 13:16
  • $\begingroup$ @MichaelStocker, darn; yes. $\endgroup$ – Lebes Feb 17 '15 at 13:16
  • 2
    $\begingroup$ Also $11! = 11\cdot 10!$ not $22\cdot 10!$. $\endgroup$ – Thomas Feb 17 '15 at 13:17
  • 2
    $\begingroup$ You have written 11!=11*10*9*...*2*1=22*10!. here this is wrong $\endgroup$ – Singh Feb 17 '15 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 '15 at 14:01
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.

| cite | improve this answer | |
$\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.