# Product of quadratic residues mod p $\equiv 1$ mod p iff $p \equiv 3$ mod 4

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.

## 2 Answers

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

• 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? – Numbersandsoon Oct 30 '13 at 3:37
• $k^2 \equiv (-1)\cdot k\cdot (p-k)$. So it's $(-1)^{(p-1)/2}(p-1)!$. – Daniel Fischer Oct 30 '13 at 9:32
• Thank you!! That's a nice way to do it :) – Numbersandsoon Oct 30 '13 at 13:01

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$