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.

 

[blue_raver22]

Sure, I would be happy to provide some guidance for this proof. First, let's break down the given equation and understand what it means.

(p-1)(p-2)...(p-r) == (-1)^r*r!(mod p)

This equation is essentially stating that the product of (p-1)(p-2)...(p-r) is congruent to (-1)^r*r! (the factorial of r) modulo p. In other words, when we divide the product of (p-1)(p-2)...(p-r) by p, the resulting remainder will be equal to (-1)^r*r!.

To start the proof, let's consider the case when r=1. In this case, the equation becomes:

(p-1) == (-1)^1*1! (mod p)

We can simplify this to:

(p-1) == -1 (mod p)

This is true because when we divide (p-1) by p, the remainder will always be -1. This is because p is one more than a multiple of p, so when we subtract 1 from it, we get a multiple of p with a remainder of -1.

Now, let's move on to the case when r=2. The equation becomes:

(p-1)(p-2) == (-1)^2*2! (mod p)

Simplifying this, we get:

(p-1)(p-2) == 1*2 (mod p)

Again, this is true because when we divide (p-1)(p-2) by p, the remainder will always be 2. This is because p is two more than a multiple of p, so when we subtract 2 from it, we get a multiple of p with a remainder of 2.

We can continue this pattern for all values of r, and we will see that the equation (p-1)(p-2)...(p-r) == (-1)^r*r! (mod p) holds true for all values of r from 1 to p-1.

To formally prove this, we can use mathematical induction. We have already shown that the equation holds true for r=1 and r=2. Now, assuming that the equation holds true for some arbitrary value of r, we can show that it also holds true for r+1.

When r+1, the equation becomes:

(p-1)(