# Thread: Congruence Proof using Wilson's Theorem

1. ## Congruence Proof using Wilson's Theorem

Dear all,

I'm having trouble completing the proof for the following result, that requires Wilson's Theorem. I've shown this, along with my work, below.

Thank you!

scherz0

--------

For any odd prime $p$, show that:
$1^2 \cdot 3^2 \cdot ... \cdot (p - 2)^2 \equiv 2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv (-1)^{\frac{p+1}{2}}$

Work: By Wilson's Theorem, I know that: $p$ prime $\Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p}$.

Also, for any $k$, I know that $p - k \equiv -k\pmod {p}$. This means that:

$p - 1 \equiv -1\pmod {p}, p - 2 \equiv -2\pmod {p}, p - 3 \equiv -3\pmod {p} \implies (p - 1)(p - 2)(p - 3)... \equiv (-1)(-2)(-3)... \pmod{p}$

But I can't see how to apply the results above to prove the congruence relation?

2. Originally Posted by scherz0
Dear all,

I'm having trouble completing the proof for the following result, that requires Wilson's Theorem. I've shown this, along with my work, below.

Thank you!

scherz0

--------

For any odd prime $p$, show that:
$1^2 \cdot 3^2 \cdot ... \cdot (p - 2)^2 \equiv 2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv (-1)^{\frac{p+1}{2}}$

Work: By Wilson's Theorem, I know that: $p$ prime $\Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p}$.

Also, for any $k$, I know that $p - k \equiv -k\pmod {p}$. This means that:

$p - 1 \equiv -1\pmod {p}, p - 2 \equiv -2\pmod {p}, p - 3 \equiv -3\pmod {p} \implies (p - 1)(p - 2)(p - 3)... \equiv (-1)(-2)(-3)... \pmod{p}$

But I can't see how to apply the results above to prove the congruence relation?

RHS, working all the time with arithmetic modulo p:

$\displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot 4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]=$

$\displaystyle{=(-1)^{\frac{p-1}{2}}(p-1)!=(-1)^{\frac{p+1}{2}}$

Now you do the LHS...

Tonio

3. Originally Posted by tonio
RHS, working all the time with arithmetic modulo p:

$\displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot 4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]$
$\displaystyle{=(-1)^{\frac{p-1}{2}}(p-1)!=(-1)^{\frac{p+1}{2}}$

Now you do the LHS...

Tonio

However, could you explain more on:

$\displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot 4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]?$

From what I see, I think that we are separating the powers so that:

$2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv 2\cdot 4 ... \cdot (p - 1) \cdot 2 \cdot 4 \cdot ... \cdot (p - 1) \pmod {p}$.

But why are there:

1) a $(p - 3)$ after the two $(p - 1)$s and

2) $-(p - 2)$, since your post was about the RHS only?