5
$\begingroup$

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 5

4

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

  • 0
    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}$.2012-09-18
2

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

\begin{equation} 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 \end{equation}

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

1

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

1

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.

1

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