5
$\begingroup$

This is a homework question.

I know there exists infinitely many primes. Let $n = p-1$ and so by Wilson's theorem we know there exists atleast one prime $p$ that divides $n! + 1$. I used wolframalpha and checked for a couple of $n = p-1$ values and all show me that there are in fact two distinct primes and one of them is in fact $p$.

How can I use this to conclude there exists a second prime $q$, $q \neq p$ such that $q$ dividies $n!+1$

$\endgroup$
3
$\begingroup$

Equivalently you can show that $(p-1)!+1=p^n$ has no solution for $p \geq 7$ and $n \in \mathbb{N}.$

Hint: $p^{n-1}+...+p+1=(p-2)!$ and $p-1|(p-2)!$ (since $p-1$ is composite), so what can you say about $n$ then? can you derive a contradiction?

$\endgroup$
  • $\begingroup$ why is showing the statement $(p-1)! + 1 = p^n$ has no solutions equivalent? And anything special about $p =7$ and $n=2$? $\endgroup$ – Tyler Hilton Feb 14 '13 at 5:13
  • $\begingroup$ You have set $n=p-1$ so if you could rule out the existence of primes where $(p-1)!+1$ is only divisible by one prime you'd be done. That bounds come from the an inequality you'll get after determining a condition on $n.$ $\endgroup$ – Ehsan M. Kermani Feb 14 '13 at 5:20
  • 1
    $\begingroup$ What is $p^{n-1}+...+p+1$ mod $p-1?$ $\endgroup$ – Ehsan M. Kermani Feb 14 '13 at 5:44
  • 1
    $\begingroup$ No, you have $n$ $1$'s, right? $\endgroup$ – Ehsan M. Kermani Feb 14 '13 at 6:23
  • 1
    $\begingroup$ Second step: Assume the contrary that there is a $p>5$ s.t. for some $n$ we have $(p-1)!+1=p^n$ or indeed $(p-1)!=p^n-1=(p-1)(p^{n-1}+...+p+1)$ which is $(p-2)!=p^{n-1}+...+p+1.$ As you said, $p^{n-1}+...+p+1$ mod $p-1$ is $n$ and since $p-1|(p-2)!$ then $p-1|n$ and indeed $p-1 \leq n.$ Thus, it is enough to show that for $p>5,$ we have $p^{p-1}>(p-1)!+1.$ $\endgroup$ – Ehsan M. Kermani Feb 14 '13 at 7:31

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.