# $p$ a prime, $p \equiv 3 \pmod 4$. Prove that $\frac{p-1}{2}! \equiv \pm 1 \pmod p$

Let $p$ be a prime, $p \equiv 3 \pmod 4$. Prove that $\frac{p-1}{2}! \equiv \pm 1 \pmod p$.

This is an exercise in one of my lecture notes. I couldn't seem to figure out how to do it. We've just covered Wilson's Theorem, Euler's phi function, and the set of least-modulus residues.

Would appreciate a solution. Lecturer doesn't provide answers unless I arrange a consultation session.

-

## 5 Answers

I will give a concrete example, and you can do the rest. Let $p=19$.

Note that $18\equiv -1\pmod{19}$. Also, $17\equiv -2\pmod{19}$, and $16\equiv -3\pmod{19}$, and so on. Finally, $10\equiv -9\pmod{19}$.

Thus $$18!\equiv \left[(1)(2)(3)\cdots(9)\right]\left[(-9)(-8)(-7)\cdots (-1)\right]\pmod{19}.$$ It follows that $(9!)^2 (-1)^9 \equiv 18!\pmod{19}$.

By Wilson's Theorem, we have $18!\equiv -1\pmod {19}$. Also, $(-1)^9=-1$. We conclude that $$(9!)^2 \equiv 1\pmod{19}.$$ It follows that $9!\equiv \pm 1\pmod{19}$.

The general case is essentially the same. The key fact is that $\dfrac{p-1}{2}$ is odd, so we get an odd number of $-1$.

-
In the general case, $\frac{p-1}{2}$ isn't odd though? e.g. p = 17 – confused Sep 18 '12 at 1:15
Oh! but it is, when p $\equiv$ 3(mod 4). I see! – confused Sep 18 '12 at 1:17
Yes, the condition that $p$ is of the form $4k+3$ is necessary for the argument to go through. The result is simply falso if $p\equiv \pmod{4}$. – André Nicolas Sep 18 '12 at 1:20

Since $p$ is odd, $p-1$ is even. Note that $\frac{p-1}{2}$ is odd. Now the product of the numbers $1$ through $p-1$ (mod $p$) is congruent to

$$1 \times 2 \times \cdots \times \frac{p-1}{2} \times -1 \times -2 \times \cdots \times -\frac{p-1}{2} = - [(\frac{p-1}{2})!]^2$$

Pairing each $i \in \{2, \cdots, p-2\}$ with its inverse mod $p$, we get $1 \times \cdots \times p-1 \equiv -1$ (mod $p$). Thus, $[(\frac{p-1}{2})!]^2 \equiv 1$ (mod $p$), and so $(\frac{p-1}{2})! \equiv \pm 1$ (mod $p$).

-

$\begin{eqnarray} {\bf Hint}\ \ \mod\ 7\!:\ -1 \,\equiv\, 6! \,&\equiv&\, 1\cdot 2\cdot 3\cdot\ \ \: 4&\cdot&\ \ \: 5&\cdot&\ \ \: 6\\ &\equiv&\, 1\cdot 2\cdot 3\cdot -3&\cdot& -2&\cdot& -1\\ &\equiv&\, -\, 3!^2\end{eqnarray}$

Hence $\rm\:3!^2\equiv1\:\Rightarrow\:3!\,\equiv\, \pm1,\:$ since, in a field, $\rm\:x^2 = 1 \iff (x\!-\!1)(x\!+\!1)=0\iff x = \pm 1.$

Remark $\$ The above method of pairing up each factor with its negation (additive inverse) is a prototypical example of exploiting reflection (involution) symmetry.

-

Suppose that $\varpi=\frac{1}{2}(p-1).$ By $$(p-1)!=1\cdot2\cdots\frac{1}{2}(p-1)\{p-\frac{1}{2}(p-1)\}\{p-\frac{1}{2}(p-3)\}\cdots(p-1)\equiv(-1)^\varpi(\varpi!)^2(\bmod p),$$ it follows, by Wilson's theorem, that $$(\varpi)^2\equiv(-1)^{\varpi-1}(\bmod p).$$ Now we need to distinguish the two cases $p=4n+1$ and $p=4n+3$.

If $p=4n+3$ as in your question, then $$(\varpi!)^2\equiv1(\bmod p),$$ $$\varpi!\equiv\pm1(\bmod p).$$ Since $-1$ is anon-residue of $p$, thr sign in the above conruence ispositive or negative according as $\varpi!$ is a residue or non-residue of $p$.

As we knew it, a product of two residues or non-residues of $p$ is also a residue, while the product of one residue and a non-residue of $p$ is no longer a residue. Therefore, the sign is positive or negative according as the number of non-residues of $p$ less than $\frac{1}{2}p$ is even or odd.

The case $p=4n+1$ remains nearly the same argument.

-

Since $x\equiv-1\cdot(p-x)\pmod{p}$, we have $$\color{#C00000}{1}\cdot\color{#00A000}{2}\cdot\color{#0000FF}{3}\cdots\color{#E07C00}{\frac{p-1}{2}}\equiv(-1)^{(p-1)/2}\color{#E07C00}{\frac{p+1}{2}}\cdots\color{#0000FF}{(p-3)}\cdot\color{#00A000}{(p-2)}\cdot\color{#C00000}{(p-1)}\tag{1}$$ multiply both sides of $(1)$ by the left side of $(1)$, then use Wilson's Theorem \begin{align} {\large\left(\tfrac{p-1}{2}!\right)^2} &\equiv(-1)^{(p-1)/2}(p-1)!\\ &\equiv-1\cdot-1\\ &\equiv1\pmod{p}\tag{2} \end{align} and since $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, $(2)$, which is $\left(\tfrac{p-1}{2}!-1\right)\left(\tfrac{p-1}{2}!+1\right)\equiv0\pmod{p}$, implies $${\large\tfrac{p-1}{2}!}\equiv\pm1\pmod{p}\tag{3}$$

-