A friend asked me this question:

If $p$ is a prime, prove that $(p - 1)! + 1$ is a power of $p$ if and only if $p = 2, 3$ or $5$.

Clearly one direction is obvious, namely that $p=2,3,5$ implies $(p - 1)! + 1$ is a power of $p$.

The other direction is not clear to me. Since by Wilson's theorem $p$ divides $(p - 1)! + 1$ so we need to show that if there are no other prime factors then $p=2,3,5$. Can someone give me a hint for establishing this?

Thanks

up vote 18 down vote accepted

Let $p^k - 1 = (p-1)!$. Cancel the factor of $(p-1)$, we get $$p^{k-1} + \cdots + 1 = (p-2)!$$ Now consider mod $p-1$ to get information about $k$. When can the equality ever hold?

  • Can you be a little more explicit? What do you mean by considering mod $p-1$ to get information about $k$? – Shahab Jan 27 '13 at 13:36
  • 2
    @shahab, show that when $p > 5$, left hand side = k mod $p-1$ while RHS = 0 mod $p-1$. Show that this implies $k \ge p-1$. – user27126 Jan 27 '13 at 19:54

Not sure if only one hint would help, you could try using more hints as needed. First, the statement holds for all natural numbers $n \notin \{2, 3, 5\} $, not just for primes. One way to proceed is to show that for $n > 5$:
1) $n$ cannot be even if it satisfies the equation
2) for $n$ odd, $(n-1)^2 \space | \space (n-1)!$
3) from (2) above and the given equation, show $(n-1) \space | \space k$ which implies $n-1 \le k$
4) show that $\forall n > 2, (n-1)! < n^{n-1} - 1$

Hope that helps!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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