Wilson's theorem proofing questions?

Printable View

May 8th 2012, 01:27 PM
Laban

Wilson's theorem proofing questions?

I've been asked to prove these 2 things :

1. $(-1)^{\frac{n-1}{2}}(1\cdot2\cdot\cdot\cdot(\frac{n-1}{2}))^{2} = -1$

2. if $n\equiv1 (mod 4)$ then x²=-1 has a solution.

I haven't manage to come by enough examples of Wilson's theorem, so I'm really in the dark here.
Any help will be much appreciated.

Thanks.
May 8th 2012, 06:18 PM
wsldam

Re: Wilson's theorem proofing questions?

I will prove when 'n' is an odd prime (so we can invoke Wilson's Theorem).

Let p be an odd prime. Then by Wilson's Theorem:

$-1 \equiv (p-1)! mod p$
$-1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot \frac{p+1}{2} \cdot ... \cdot (p-1) mod p$
Since $p \equiv 0 mod p$ we can freely subtract p from each term in the second half of the previous equation. This gives us:
$-1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot (-\frac{p-1}{2} \cdot ... \cdot (-1)) mod p$
Now note that in the second half of the right hand side there are $\frac{p-1}{2}$ '-1's' (pardon my notation abuse). Pulling out the '-1's' we have the result.

If $p \equiv 1 mod 4$ then $\frac{p-1}{2} \equiv 0 mod 2$ . Hence, by our previous result, $-1 \equiv [(\frac{p-1}{2})!]^2 mod p$ . Therefore $x^2 \equiv -1 mod p$ has a solution.
May 8th 2012, 08:20 PM
princeps

Re: Wilson's theorem proofing questions?

Wilson's Theorem Proof
May 9th 2012, 03:41 PM
Laban

Re: Wilson's theorem proofing questions?

Quote:

Originally Posted by wsldam

I will prove when 'n' is an odd prime (so we can invoke Wilson's Theorem).

Let p be an odd prime. Then by Wilson's Theorem:

$-1 \equiv (p-1)! mod p$
$-1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot \frac{p+1}{2} \cdot ... \cdot (p-1) mod p$
Since $p \equiv 0 mod p$ we can freely subtract p from each term in the second half of the previous equation. This gives us:
$-1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot (-\frac{p-1}{2} \cdot ... \cdot (-1)) mod p$
Now note that in the second half of the right hand side there are $\frac{p-1}{2}$ '-1's' (pardon my notation abuse). Pulling out the '-1's' we have the result.

If $p \equiv 1 mod 4$ then $\frac{p-1}{2} \equiv 0 mod 2$ . Hence, by our previous result, $-1 \equiv [(\frac{p-1}{2})!]^2 mod p$ . Therefore $x^2 \equiv -1 mod p$ has a solution.

Thanks a lot! I would have never figured it out on my own. I'm still baffled as to why we're getting these questions in a linear algebra course.