Congruence Proof using Wilson's Theorem

Printable View

April 10th 2011, 03: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 $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?
April 10th 2011, 08: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 $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
April 11th 2011, 09:08 AM
scherz0

Quote:

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

Thanks for your response, 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?