# 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