Prove that $\left( \frac{p-1}{2} \right)! \equiv (-1)^n \mod p$, $n$ is quad. nonres. of $p$ $< p/2$.

Let $p$be a prime number with $p \equiv 3 \mod 4$. Prove that $\left( \frac{p-1}{2} \right)! \equiv (-1)^n \mod p$ where $n$ is the number of positive integers less than $p/2$ that are quadratic nonresidues of $p$.

I have tried solving this problem using the fact that $\left( \frac{p-1}{2}\right)! \equiv \pm 1 \mod p$ if and only if $p \equiv 3 \mod 4$. But I can't seem to bring the logic with the $n$ into the picture. Can you help?

$$1 \equiv \left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv \prod_{k=1}^{\frac{p-1}{2}}k^2.$$
Now write the squares $> \frac{p-1}{2}$ as $k^2 = p-r$ with $r \leqslant \frac{p-1}{2}$. Count the $-1$s.
• Aha, so is the idea that since all of the $(p-1)/2$ quadratic residues are congruent to $1^2,2^2,3^2,\ldots,[(p-1)/2]^2$, the squares outside this set must be quadratic nonresidues? But in the product $\prod_{k=1}^{(p-1)/2} k^2$ I don't see any squares out of this set. – Numbersandsoon Nov 5 '13 at 20:37
• No, if the residue of $k^2$ is $> \frac{p-1}{2}$, then write $k^2 = p-r_k$ with $r_k \leqslant \frac{p-1}{2}$. Otherwise, write $k^2 = r_k$ with $r_k \leqslant \frac{p-1}{2}$. Then you have $$1 \equiv \prod_{k=1}^{(p-1)/2} \pm r_k = (-1)^n\prod_{k=1}^{(p-1)/2}r_k.$$ Now look sharp to see that that is exactly the equation you want. – Daniel Fischer Nov 5 '13 at 20:47