3
$\begingroup$

Show $[(p-1)!]^{p^{n-1}} \equiv -1 $ (mod $p^n$) for n $\in \mathbb N$, by induction. p a prime and p>2.

I can't seem to prove the inductive step for this. Would appreciate help.

My approach has been:

n=1 is just from Wilson.

Assume true for n=m: $[(p-1)!]^{p^{m-1}} \equiv -1 $ (mod $p^m$)

Then,

$[(p-1)!]^{p^{(m+1)-1}} = ([(p-1)!]^{p^{m-1}})^p \equiv (-1)^p \equiv -1$ (mod $p^m$)

But, how do I get this to say anything in terms of mod $p^{m+1}$? Since I need the RHS to end up as: -1 (mod $p^{m+1}$).

One thing I could draw from this congruence is that $[(p-1)!]^{p^{(m+1)-1}}$ is not a multiple of p, since multiples of p must be greater than -1 apart from each other.

Hence, GCD($[(p-1)!]^{p^{(m+1)-1}}, p^{m+1})=1.$ I wasn't sure how I might use this.

Alternatively, I could express it as: $[(p-1)!]^{p^{(m+1)-1}} = [(p-1)!]^{p^m}$. But this didn't seem the right way to go about it, since by cancelling the -1+1, there doesn't seem to be any way to use the inductive hypothesis/assumption above.

Another useful result might be that: GCD((p-1)!,$p^{m+1}$)=1.

  • 2
    Hint: If $x\equiv -1 \pmod {p^{m-1}}$ show that $x^p\equiv -1 \pmod {p^m}$ when $p$ is an odd prime, when $m>1$2012-09-24

2 Answers 2

2

Hint: More generally, if $x\equiv -1\pmod {p^{m-1}}$ then $x^p \equiv -1 \pmod {p^m}$ for $m>1$ and $p$ an odd prime.

  • 0
    Thanks @Thomas. how do you derive this result?2012-09-24
  • 0
    Showing this is roughly the same as Martini's answer, namely, that if $x=pk-1$ then using the binomial theorem.2012-09-24
  • 0
    Am I able to do it without the binomial though? The notes that I saw this problem in don't touch on binomial expansion.2012-09-24
  • 0
    Alternatively, you could write $x^p+1 = (x+1)(x^{p-1}-x^{p-2}+x^{p-3}...)$ and note that the terms of $x^{p-1}-x^{p-2}+...$ have to add up to something divisible by $p$.2012-09-24
  • 0
    In this case, couldn't (x+1) be divisible by p instead?2012-09-24
  • 0
    @jack, we assumed $x\equiv -1 \pmod {p^{m-1}}$, so $x+1$ is divisible by $p^{m-1}$. What you need to prove is that the other term of the product is always divisible by $p$ to show that $x^p+1$ is divisible by $p^m$.2012-09-24
  • 0
    @ThomasAndrews Oh! That makes sense.2012-09-24
  • 0
    Showing that $(x^{p-1}-x^{p-2}+x^{p-3}...)$ is divisible by p, doesn't look any easier of a task.2012-09-24
  • 0
    This is great, thanks very much.2012-09-24
  • 0
    @confused : Since $x \equiv -1 \mod p$, then $x^{p-1} - x^{p-2} + \ldots - x + 1 \equiv 1 + 1 + \ldots 1 + 1 \equiv 0 \mod p$.2012-09-24
1

$(p-1)!^{p^{n-1}} = kp^n - 1$ for some $k\in \mathbb Z$ by induction hypothesis, so \begin{align*} (p-1)!^{p^n} &= \bigl((p-1)!^{p^{n-1}}\bigr)^p\\ &= (kp^n - 1)^p\\ &= \sum_{l=0}^p \binom{p}l (kp^n)^l(-1)^{p-l}\\ &= (-1)^p + p \cdot kp^n(-1)^{p-1} + k^2p^{2n}\sum_{l=2}^p \binom pl (kp^n)^{l-2}(-1)^{p-l}\\ &\equiv (-1)^p + 0 + 0\\ &= -1 \pmod{p^{n+1}} \end{align*} and we are done.

  • 0
    I don't really understand the use of combinations like this.2012-09-24
  • 0
    Better now?${}{}$2012-09-24
  • 0
    Thanks. @martini I can follow it better now. In the term, $k^2p^{2n}\sum_{l=2}^p \binom pl (kp^n)^{l-2}(-1)^{p-l}$, wouldn't some of the terms of this sum be non-integer fractions, since $\binom pl$ can be a non-integer fraction? Won't this create a problem when working modulo $p^{n+1}$?2012-09-24
  • 2
    $\binom{n}{k}$ is always an integer, since it is the **number** of ways to choose a committee of $k$ people from a group of $n$ people.2012-09-24