# Show $[(p-1)!]^{p^{n-1}} \equiv -1$ (mod $p^n$) for n $\in \mathbb N$

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.

-
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$ –  Thomas Andrews Sep 24 '12 at 20:25

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.

-
Thanks @Thomas. how do you derive this result? –  confused Sep 24 '12 at 20:48
Showing this is roughly the same as Martini's answer, namely, that if $x=pk-1$ then using the binomial theorem. –  Thomas Andrews Sep 24 '12 at 20:53
Am I able to do it without the binomial though? The notes that I saw this problem in don't touch on binomial expansion. –  confused Sep 24 '12 at 20:55
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$. –  Thomas Andrews Sep 24 '12 at 20:55
In this case, couldn't (x+1) be divisible by p instead? –  jack Sep 24 '12 at 21:04

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

-
I don't really understand the use of combinations like this. –  confused Sep 24 '12 at 20:48
Better now?${}{}$ –  martini Sep 24 '12 at 21:01
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}$? –  confused Sep 24 '12 at 21:36
$\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. –  André Nicolas Sep 24 '12 at 21:50