# Congruence Proof using Wilson's Theorem

• Apr 10th 2011, 02:15 PM
scherz0
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 $\displaystyle p$, show that:
$\displaystyle 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: $\displaystyle p$ prime $\displaystyle \Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p}$.

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

$\displaystyle 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?
• Apr 10th 2011, 07:14 PM
tonio
Quote:

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 $\displaystyle p$, show that:
$\displaystyle 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: $\displaystyle p$ prime $\displaystyle \Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p}$.

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

$\displaystyle 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 \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 \displaystyle{=(-1)^{\frac{p-1}{2}}(p-1)!=(-1)^{\frac{p+1}{2}}$

Now you do the LHS...

Tonio
• Apr 11th 2011, 08:08 AM
scherz0
Quote:

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

$\displaystyle \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 \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 \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:

$\displaystyle 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 $\displaystyle (p - 3)$ after the two $\displaystyle (p - 1)$s and

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