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.

  • 4
    $\begingroup$ Write $(p-1)! = [(p-1)(p-2)...(p-k)](p-(k+1))!$ then reduce each of the first $k$ brackets mod $p$. $\endgroup$ – fretty Aug 6 '14 at 17:29
  • $\begingroup$ The first part reduces to $-1$, $-2$, etc correct? $\endgroup$ – emka Aug 6 '14 at 17:33
  • $\begingroup$ Yes, so overall what will you get? $\endgroup$ – fretty Aug 6 '14 at 17:34
  • $\begingroup$ -k!(p-(k+1))! I believe $\endgroup$ – emka Aug 6 '14 at 17:35
  • $\begingroup$ Not exactly...it could be either of $\pm k!(p-(k+1))!$. You only know how many minus signs there are. $\endgroup$ – 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")

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ Very interesting indeed. I can see an alternative proof of $p\mid2^{p-1}-1$ showing up... $\endgroup$ – Bart Michels Aug 6 '14 at 18:12
  • $\begingroup$ Alternatively the end congruence gives a proof of the binomial coeff congruence at the top. $\endgroup$ – fretty Aug 6 '14 at 21:16
  • $\begingroup$ Sure, but it's really much easier to prove directly what $\binom{p-1}{k}=(-1)^{k}$, which doesn't even require Wilson. @fretty $\endgroup$ – Thomas Andrews Aug 6 '14 at 21:19
  • $\begingroup$ I think (mod $k$) should be (mod $p$) in the first line. $\endgroup$ – Tad Jan 31 '15 at 20:58
  • $\begingroup$ Yep, thanks @Tad. $\endgroup$ – 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.

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

| cite | improve this answer | |
  • 1
    $\begingroup$ +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. $\endgroup$ – Gone Aug 6 '14 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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