Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Why is the square of all odds less than an odd prime $p$ congruent to $(-1)^{(p+1)/(2)}\pmod p$?
If p is an odd prime, prove that $1^2 \times 3^2 \times 5^2 \cdots \times (p-2)^2 \equiv (-1)^{(p+1)/2}\pmod{p}$

I'd love your help with proving the following claim:

For prime $p>2$:

$$1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p.$$

I instantly thought of Wilson Theorem which says that $1\cdot2\cdot3\cdot\cdot\cdot\cdot(p-1) \equiv (-1) \pmod p$, but I can't see how to use it.

I also tried to divide it to two cases, for $p \equiv 1 \pmod4$, and $p \equiv 3 \pmod4$, but again I didn't reach the conclusion.

Thanks a lot!

share|improve this question

marked as duplicate by Marvis, Jozef, Jyrki Lahtonen, Gerry Myerson, t.b. Jun 30 '12 at 0:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Thats not Wilson's theorem. Check –  pritam Jun 29 '12 at 17:52
    
On the right-hand side of the page your problem is on, there is a link to a solution of the same problem. The same problem also came up fairly recently. I think I was even one of the people who answered, but of course can't find a link to that. –  André Nicolas Jun 29 '12 at 17:53
    
@AndréNicolas Just curious. Why didn't you vote to close this question? –  user17762 Jun 29 '12 at 18:12
    
@Jozef: Note that for $p\equiv 1\pmod{4}$, this gives an explicit (though not computationally useful) formula for an $x$ such that $x^2\equiv -1\pmod{p}$. –  André Nicolas Jun 29 '12 at 18:13
    
@Marvis: I am generally not in favour of closing questions. My comment about the duplication was just meant to help the OP find an answer. –  André Nicolas Jun 29 '12 at 18:16

4 Answers 4

up vote 1 down vote accepted

You know that

$(p-1)! \equiv -1 \mod p$

Then, since $p-k\equiv -k \mod p$ we have

$$-1=(p-1)! =[1 \cdot 3 \cdot 5 \cdot ... \cdot (p-2)] \cdot [ 2 \cdot 4 ... \cdot (p-1)]$$ $$=[1 \cdot 3 \cdot 5 \cdot ... \cdot (p-2)] \cdot [ (p-2) \cdot (p-4) ... \cdot (1) \cdot (-1)^\frac{p-1}{2}] $$

share|improve this answer
    
yup, typo.thank you. –  N. S. Jun 29 '12 at 19:33

It isn't true. Take $p = 5$, then $1^2 3^2 \equiv -1 \not \equiv 1 \equiv (-1)^\frac{5-1}{2} \pmod 5$

share|improve this answer
    
Oh sorry, it's suppose to be $p+1$ in the power of $(-1)$. Any way please delete the answer so I could delete the question, since it has already been posted here. –  Jozef Jun 29 '12 at 18:05

Since $p$ is odd, the negatives of the odd residues listed in your product are the even residues: $-1=p-1\pmod{p}$, $-3=p-3\pmod{p}$, $-5=p-5\pmod{p}$, etc.

By Wilson's Theorem, the product of all of these non-zero residues is $(p-1)!=-1\pmod{p}$.

Your product can be changed to $(p-1)!$ by $$ \begin{align} \color{#C00000}{1^2}\cdot\color{#00A000}{3^2}\cdot\color{#0000FF}{5^2}\cdots(p-2)^2 &=(-1)^{\frac{p-1}{2}}\color{#C00000}{1\cdot(p-1)}\cdot\color{#00A000}{3\cdot(p-3)}\cdot\color{#0000FF}{5\cdot(p-5)}\cdots(p-2)\cdot2\\ &=(-1)^{\frac{p-1}{2}}(-1)\\ &=(-1)^{\frac{p+1}{2}}\pmod{p} \end{align} $$

share|improve this answer

$ 1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p-1}{2}} \pmod p $

is the same as

$ 1^22^23^2\cdot\cdot\cdot((p-1)/2)^2 \equiv (-1)^{\frac{p-1}{2}} \pmod p $

since we are working modulo p.

Now we can split each square itself as $ i^2 = i(p-i)(-1) $

$(-1)^{\frac{p-1}{2}} 123\cdot\cdot\cdot(p-1)\equiv (-1)^{\frac{p+1}{2}} \pmod p $

from Wilson's theorem.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.