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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


I think I have figured out a proof to this problem:

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


Not the answer you're looking for? Browse other questions tagged or ask your own question.