If $p\equiv3\pmod4$, and $n$ is the number of quadratic residues less than $p/2$, how can I show that $2\cdot4\cdots(p-1)\equiv(-1)^{n+k}$?

Question

If $p$ is congruent to $3 \pmod 4$, and $n$ is the number of quadratic residues less than $p/2$, how can I show that $2\cdot 4\cdot 6\cdots (p-1)$ is congruent to $(-1)^{n+k}$ modulo $p$?

So $p=4k+3$ and I know $(-1/p)$ is congruent to $(-1)^{(p-1)/2}$ etc but can't think of a way to show the product of the even numbers is congruent to $(-1)^{n+k}$. Any hints/help would be much appreciated.

Answer 1

You can write the product as $2^{(p-1)/2}$ times $(\frac{p-1}2)!$ and treat both factors separately:

Quadratic reciprocity for $q=2$ + Gauss' criterion gives $2^{(p-1)/2}\equiv(-1)^{k+1}$.

Because $p\equiv3\pmod4$, the product of quadratic residues is $1$ (each quadratic residue comes with its inverse, and $-1$ isn't one of them). There are $(p-1)/2$ nonzero QR in total (odd number). By sending a QR $a$ to $p-a$ if it's $>p/2$, their product gets multiplied by $(-1)^{(p-1)/2-n}=(-1)^{n+1}$. The result equals $(\frac{p-1}2)!$, because there are $(p-1)/2$ QR's and $a$ and $p-a$ cannot simultaneaously be one.

Answer 2

Since $p\equiv 3 \bmod 4$ (equivalently $p=4k+3$), we have $\phi(p)=p-1\equiv 2\bmod 4$ and $r:=\phi(p)/2$ is odd.

So for any primitive root $g$, we have $g^r\equiv -1$ which is thus not a quadratic residue since only even powers of $g$ are quadratic residues, meaning that exactly one of each pair $a = g^\ell$ and $-a = g^{\ell+r}$ is a quadratic residue.

Then within the desired product $e:=2\cdot 4\cdots (p-1)$, which has $r$ terms, there is exactly one of any given $a$ and $-a$. Multiplying by $(-1)^{(r+1)/2} = (-1)^{(p+1)/4}$ will give us the expression $e' = e\cdot(-1)^{(r+1)/2} \equiv 1\cdot2\cdots r$, and then multiplying again by $(-1)^{r-n}$ will give us the product of all quadratic residues (by changing the non-residues to their quadratic counterparts), $e''= e\cdot (-1)^{p+1)/4+r-n}$.

Then $e'' \equiv g^{\sum_1^r 2i} \equiv g^{r(r+1)} \equiv 1 \bmod p$ (since $r{+}1$ is even). Then since $(-1)^{-a} = (-1)^a$, $e \equiv (-1)^{(p+1)/4+r+n}$ and since only parity matters $e \equiv (-1)^{(p-3)/4+n} \equiv (-1)^{n+k}\bmod p$