# If $p \equiv 3 \ (\text{mod} \ 4)$ is a prime, show $(\frac{p-1}{2})! \equiv (-1)^{t} \ (\text{mod} \ p)$ [duplicate]

This question already has an answer here:

If $$p \equiv 3 \ (\text{mod} \ 4)$$ is a prime, show $$(\frac{p-1}{2})! \equiv (-1)^{t} \ (\text{mod} \ p),$$ where $$t$$ is number of positive integers less than $$\frac{p}{2}$$ that are nonquadratic residues of $$p.$$

My attempt: Since $$p-1 \equiv -1, \ p-2 \equiv -2, ..., p-(\frac{p-1}{2}) \equiv \frac{p-1}{2} \ (\text{mod} \ p)$$ and $$1 \equiv 1, \ 2\equiv 2,..., \frac{p-1}{2} \equiv \frac{p-1}{2} \ (\text{mod} \ p),$$ it follows that $$((\frac{p-1}{2})!)^2 \equiv-(p-1)! \equiv 1,$$ by Wilson's theorem.

I am not sure how to continue from here. How do I relate it to $$t?$$ Appreciate if anyone could advise. Thank you.

## marked as duplicate by user10354138, Alexander Gruber♦Nov 7 '18 at 7:26

Since $$1 \equiv 1, \ 2\equiv 2,..., \frac{p-1}{2} \equiv \frac{p-1}{2} \ (\text{mod} \ p)$$ and $$p-(\frac{p-1}{2}) \equiv -\frac{p-1}{2} \ (\text{mod} \ p), ..., p-2 \equiv -2, p-1 \equiv -1$$ ,it follows that $$(-1)^{\frac{p-1}{2}}((\frac{p-1}{2})!)^2 = -((\frac{p-1}{2})!)^2 \equiv(p-1)!.$$ By Wilson's theorem, $$((\frac{p-1}{2})!)^2 \equiv 1 \ (\text{mod} \ p).$$
Suppose $$1^2 \equiv a_1, ..., (\frac{p-1}{2})^2 \equiv a_n \ (\text{mod} \ p).$$ Then $$a_1,...,a_n$$ are all the distinct $$\frac{p-1}{2}$$ quadratic residues modulo $$p.$$
Given $$a$$ such that $$1 \leq a \leq \frac{p-1}{2},$$ we claim that either $$a$$ or $$-a$$ is a quadratic residue modulo $$p$$ but not both. Now, $$\Big(\dfrac{-a}{p}\Big)= \Big(\dfrac{-1}{p}\Big)\Big(\dfrac{a}{p}\Big).$$ Since $$p \equiv 3 \ (\text{mod} \ 4), \ \Big(\dfrac{-1}{p}\Big) = -1$$ and $$a \not \equiv 0 \ (\text{mod} \ p),$$ it follows that $$\Big(\dfrac{a}{p}\Big)=-\Big(\dfrac{-a}{p}\Big).$$
Hence, $$1^2 \times 2^2 \times... \times (\frac{p-1}{2})^2 = ((\frac{p-1}{2})^2)! \equiv a_1...a_n = (-1)^t (1\times 2 \times ... \times \frac{p-1}{2})= (-1)^{t}(\frac{p-1}{2})!,$$ where $$t$$ is number of nonquadratic residues modulo $$p.$$