# A consequence of Wilson's Theorem

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.

• 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 '14 at 17:29
• The first part reduces to $-1$, $-2$, etc correct? – emka Aug 6 '14 at 17:33
• Yes, so overall what will you get? – fretty Aug 6 '14 at 17:34
• -k!(p-(k+1))! I believe – emka Aug 6 '14 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 '14 at 17:36

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")

An alternative approach: $$\binom{p-1}{k} \equiv (-1)^k\pmod p\,; 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$$

• Very interesting indeed. I can see an alternative proof of $p\mid2^{p-1}-1$ showing up... – Bart Michels Aug 6 '14 at 18:12
• Alternatively the end congruence gives a proof of the binomial coeff congruence at the top. – fretty Aug 6 '14 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 '14 at 21:19
• I think (mod $k$) should be (mod $p$) in the first line. – Tad Jan 31 '15 at 20:58
• Yep, thanks @Tad. – Thomas Andrews Jan 31 '15 at 21:00

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.

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

• +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. – Gone Aug 6 '14 at 20:27