Wilson's Theorem

1. Feb 24, 2010

tarheelborn

Show that (p-1)(p-2)...(p-r)==(-1)^r*r!(mod p) for r=1, 2, ..., p-1. I am having trouble getting this proof started. Can you please give me some direction? Thank you.

2. Feb 24, 2010

mrbohn1

Well...first note that if you multiply out then every term in the resulting sum will be a multiple of p, and hence will disappear mod p. So all you really need to be concerned with is the constant term: (-1)(-2)...(-r).

3. Feb 24, 2010

tarheelborn

So something like
-1 * -2 * ... * -r == (-1)(-2)...(-r)(mod p)
== (-1)^r(1*28...*r)(mod p)
== (-1)^r * r! (mod p)
and we are done, right?

Thank you.

4. Feb 24, 2010

Tinyboss

By Fermat's Little Theorem, $$a^{p-1}-1\equiv 0$$ mod p. Define a polynomial $$p(x)=x^{p-1}-1$$, and note that $$q$$ is satisfied for x=1,2,...,p-1, and that these are all the roots.

So we can then write $$q(x)=(x-1)(x-2)\cdots(x-(p-1))$$. By changing the order of subtraction in each factor, we can make a related polynomial $$q'(x)=(1-x)(2-x)\cdots((p-1)-x)=(-1)^{n-1}q(x)$$.

What happens when we evaluate at zero? $$q'(0)=(1)(2)\cdots(p-1)=(-1)^{n-1}q(0)=(-1)^n$$. I.e., $$(p-1)!\equiv(-1)^n$$ mod p.

It's a simple step from there to the result you need.

Last edited: Feb 24, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook