3
$\begingroup$

Let $p$ be an odd prime number. Prove that the product of the quadratic residues modulo $p$ is congruent to $1$ modulo $p$ if and only if $p \equiv 3 \pmod 4$.

I've tried using the fact that any quadratic residue modulo $p$ must be one of the numbers $1,2,\ldots,p-1$. But then I got stuck. This problem should be solvable without any Legendre symbol trickiness.

$\endgroup$
6
$\begingroup$

Every quadratic residue is of the form $k^2$ for a $k \in \{1,\,\dotsc,\, \frac{p-1}{2}\}$. So the product of quadratic residues is

$$\prod_{k=1}^{\frac{p-1}{2}} k^2.$$

Now relate that to Wilson's theorem: Since $k^2 \equiv (-1)\cdot k \cdot (p-k) \pmod{p}$, we have

$$\prod_{k = 1}^{\frac{p-1}{2}}k^2 \equiv (-1)^{\frac{p-1}{2}}\prod_{k = 1}^{\frac{p-1}{2}} k \cdot \prod_{k = 1}^{\frac{p-1}{2}}(p-k) =(-1)^{\frac{p-1}{2}}\cdot (p-1)! \equiv (-1)^{\frac{p+1}{2}}\pmod{p}.$$

Thus the product of quadratic residues modulo $p$ is $\equiv 1 \pmod{p}$ if $p \equiv 3 \pmod{4}$ and it is $\equiv -1\pmod{p}$ if $p \equiv 1 \pmod{4}$.

$\endgroup$
  • $\begingroup$ I see that $\prod_{k=1}^{(p-1)/2} k^2 = \left[ \left( \frac{p-1}{2} \right) ! \right]^2$. Now to prove the "if" part we assume that $\left[ \left( \frac{p-1}{2} \right) ! \right]^2 \equiv 1 \pmod p$. But how exactly do I relate that to Wilson's theorem to conclude that $p \equiv 3 \pmod 4$? And for the "only if" part, we assume that $p \equiv 3 \pmod 4$ so $p=4k+3$. But that only reduces the factorial to $\left( 2k+2 \right)!$, how does that reduce? $\endgroup$ – Numbersandsoon Oct 30 '13 at 3:37
  • 3
    $\begingroup$ $k^2 \equiv (-1)\cdot k\cdot (p-k)$. So it's $(-1)^{(p-1)/2}(p-1)!$. $\endgroup$ – Daniel Fischer Oct 30 '13 at 9:32
  • $\begingroup$ Thank you!! That's a nice way to do it :) $\endgroup$ – Numbersandsoon Oct 30 '13 at 13:01
3
$\begingroup$

If $g$ is a primitive root $\pmod p,$

the quadratic residues are $g^{2k}$ where $2\le 2k\le p-1 $

So, the product of quadratic residues will be $$g^{2+4+\cdots+p-1}=\left(g^{\frac{p-1}2}\right)^{\frac{p+1}2}$$

As $g$ is a primitive root, $g^{\frac{p-1}2}\equiv-1\pmod p$

$\endgroup$

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.