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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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