Wilson's Theorem Proof Help for p-1 to p-r Modulo p

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

 

[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).

 

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

 

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