1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

You can write

$$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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Numbersandsoon Nov 5 '13 at 20:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Nov 5 '13 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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