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.

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$

A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$.

I was told to think of it like so,

Let $0 \leq i \leq p-1$. Then $(p-i)\equiv -i \mod p.$

I'm interested in proceeding in the above way, but I'm not sure how to.

share|improve this question
3  
Write $(p-1)! = [(p-1)(p-2)...(p-k)](p-(k+1))!$ then reduce each of the first $k$ brackets mod $p$. –  fretty Aug 6 at 17:29
    
The first part reduces to $-1$, $-2$, etc correct? –  abet Aug 6 at 17:33
    
Yes, so overall what will you get? –  fretty Aug 6 at 17:34
    
-k!(p-(k+1))! I believe –  abet Aug 6 at 17:35
    
Not exactly...it could be either of $\pm k!(p-(k+1))!$. You only know how many minus signs there are. –  fretty Aug 6 at 17:36

4 Answers 4

Hint $\ $ An equivalent way to state Wilson's theorem is that any complete system of representatives of nonzero remainders mod $\,n\,$ has product $\equiv -1.\,$ In particular this is true for any sequence of $\,p\,$ consecutive integers, after removing its $\rm\color{#c00}{multiple}$ of $\,p.\,$ Your special case is the sequence $\, -k,\,-k\!+\!1,\ldots,-1,\require{cancel}\cancel{\color{#c00}0,} 1,2,\ldots, (p\!-\!k\!-\!1),\,$ with product $(-1)^k k!\, (p\!-\!k\!-\!1)!\equiv -1.\ $ QED

Remark $\ $ The essence of Wilson's theorem is group-theoretical, so if you know a little group theory I highly recommend that you look at some prior posts on the group-theoretic viewpoint, which more clearly highlight the innate involution symmetry (negation/inversion "reflections")

share|improve this answer

An alternative approach: $$\binom{p-1}{k} \equiv (-1)^k\pmod k\,; 0\leq k\leq p-1$$ by induction, since $\binom{p-1}{k}+\binom{p-1}{k+1} = \binom{p}{k+1} \equiv 0\pmod p$ when $k<p-1$. (When $k=0$ this is obvious.)

But $\binom{p-1}{k} = \frac{(p-1)!}{k!(p-1-k)!}$ So: $$(-1)^k k!(p-1-k)! \equiv (p-1)!\equiv -1\pmod p$$

And finally:

$$k!(p-1-k)! \equiv (-1)^{k+1}\pmod p$$

share|improve this answer
    
Very interesting indeed. I can see an alternative proof of $p\mid2^{p-1}-1$ showing up... –  barto Aug 6 at 18:12
    
Alternatively the end congruence gives a proof of the binomial coeff congruence at the top. –  fretty Aug 6 at 21:16
    
Sure, but it's really much easier to prove directly what $\binom{p-1}{k}=(-1)^{k}$, which doesn't even require Wilson. @fretty –  Thomas Andrews Aug 6 at 21:19

A numerical example:

Let $p=47$. All congruences will be modulo $47$, so out of laziness we leave out the modulus. We know that $46!\equiv -1$.

Now we think about $45!$. Note that $(45!)(46)\equiv -1$. But $46\equiv -1$. Thus $$45!(-1)\equiv -1.$$ Next we think about $44!$. Note that $(44!)(45)(46)\equiv -1$. But $45\equiv -2$ and $46\equiv -1$, so $$(44!)(-2)(-1)\equiv -1,$$ or equivalently $$(44!)(-1)^2(2!)\equiv -1.$$ Next we look at $43!$. Note that $(43!)(44)(45)(46)\equiv -1$. But $44\equiv -3$, $45\equiv -2$, and $46\equiv -1$. We conclude that $$(43!)(-1)^3(3!)\equiv -1.$$ Next we look at $42!$. Since $(42!)(43)(44)(45)(46)\equiv -1$, an analysis like the ones above shows that $$(42!)(-1)^4(4!)\equiv -1.$$ Also, we have $$(41!)(-1)^5(5!)\equiv -1,$$ and so on. To get the slightly different form of the OP, in the $42!$ case multiply both sides by $(-1)^4$. In the $41!$ case, multiply both sides by $(-1)^5$. That gets rid of the minus signs on the left.

share|improve this answer

Writing $(p-1)! = (p-1)(p-2)...(p-k)(p-(k+1))!$ and reducing mod $p$ gives:

$(p-1)! \equiv (-1)^k (p-(k+1))!k! \bmod p$.

Now using Wilson's theorem gives:

$(-1)^k (p-(k+1))! k! \equiv -1 \bmod p$.

Multiplying both sides of the congruence by $(-1)^k$ gives:

$(p-(k+1))! k! \equiv (-1)^{k+1} \bmod p$.

share|improve this answer
1  
+1 I don't understand why this got no votes. It's a natural way to proceed. See also my answer which shows how to view it as arising from Wilson's Theorem applied to a different system of remainder reps. –  Bill Dubuque Aug 6 at 20:27

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.