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

  • 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