<s>[INST] $r! \equiv (−1)^k \pmod p$ Suppose that p ≡ 3 (mod 4) 
and $r = \frac {p-1}2$
Show that $r! \equiv (−1)^k \pmod p$
where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$
I know from Wilson's Theorem for a prime p:
$(p−1)! \equiv −1 \pmod p$
I don't know where to start from .. 
I managed to show that 
$r! \equiv \pm 1 \pmod p$
any help or hint will be appreciated
 [/INST] First, since $p \equiv 3$ (mod $4$), $-1$ is not a QR. $-1 \equiv g^{\frac{p-1}{2}}$ for any primitive root $g$ and $\frac{p-1}{2}$ is odd. The QRs have even exponent. 
So now take $1 \leq a \leq \frac{p-1}{2}$. Then exactly one of $a$ and $-a$ is a QR. Suppose both were QRs. Then $a \equiv x^2$ (mod $p$) and $-a \equiv y^2$ (mod $p$). What can we conclude about $-1$? Then, remember that there are $\frac{p-1}{2}$ non-zero QRs. So that ensures one of $a$ and $-a$ is a QR. 
Now $r! \equiv 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \frac{p-3}{2} \cdot \frac{p-1}{2}$ (mod $p$). For every non-quadratic residue $a$ in the product, replace $a$ with $-(-a)$ so that $-a$ is a QR. This gives:
$r! \equiv (-1)^k \cdot 1^2 \cdot 2^2 \cdot 3^2 \cdot \ldots \cdot (\frac{p-3}{2})^2 \cdot (\frac{p-1}{2})^2$ (mod $p$) because we have $\frac{p-1}{2}$ distinct quadratic residues in our product, i.e. all the quadratic residues. So $r! \equiv (-1)^k (r!)^2$ (mod $p$) and $r!$ is invertible. 
</s>