Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
show 5 more comments

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

share|improve this answer
    
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
1  
$\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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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