Exercise 3.1.17* (Find $1\cdot 3 \cdot 5\cdots(p-2)$ modulo $p$)

Question

Prove that if $p$ is a prime having the form $4k+3$, and if $m$ is the number of quadratic residues less that $p/2$, then $1\cdot 3 \cdot 5 \cdots (p-2) \equiv (-1)^{m+k+1} \pmod p$, and $2 \cdot4 \cdot 6 \cdots (p-1) \equiv (-1)^{m+k} \pmod p$.

\bigskip
Hint.  Denoting the first given product by $P$, and $(2k+1)!$ by $Q$, prove that $p\equiv (-1)^k Q \pmod p$ by using $2j \equiv -(p-2j) \pmod p$. Similarly, relate $Q$ to the product of the quadratic residues modulo $p$ by replacing any nonresidue $n$ in $Q$ by the quadratic residue $-n$, and use the preceding problem.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
Let $p$ a prime of the form $p = 4k+3$. Put
\begin{align*}
P &= 1\cdot 3\cdot 5 \cdots (p-2),\qquad Q = \left(\frac{p-1}{2}ight)! = (2k+1)!\
R &= 2\cdot4 \cdot 6 \cdots(p-1).
\end{align*}
Then, using $2j \equiv - (p-2j) \pmod p$,
\begin{align*}
P &= \prod_{j=1}^{(p-1)/2} (2j-1)\
&\equiv \prod_{j=1}^{(p-1)/2} [-(p-2j) - 1] \
& \equiv (-1)^{(p-1)/2} \prod_{j=1}^{(p-1)/2} (p- (2j+1))\
&\equiv -R \pmod p,
\end{align*}
because $\prod_{j=1}^{(p-1)/2} (p- (2j+1)) = 2\cdot 4\cdot 6\cdots (p-1) = R$, and $ (-1)^{(p-1)/2} = (-1)^{2k+1} = -1$. This proves
\begin{align}
P \equiv - R \pmod p.
\end{align}

Moreover,
\begin{align*}
R &= \prod_{j=1}^{(p-1)/2} (2j)\
&= 2^{(p-1)/2} \prod_{j=1}^{(p-1)/2} j\
&\equiv \legendre{2}{p} \left(\frac{p-1}{2}ight)!  \pmod p
\end{align*}
So
\begin{align}
R \equiv \legendre{2}{p} Q \pmod p.
\end{align}

Here $\legendre{2}{p} = 2^{(p^2-1)/2}$, where
\begin{align*}
\frac{p^2 - 1}{8} &= \frac{(4k+3)^2 - 1}{8}\
&= 2k^2 + 3k +1\
&\equiv k+1 \pmod 2.
\end{align*}
Therefore
$$\legendre{2}{p} = -(-1)^k,$$
and using (1) and (2),
\begin{align}
P \equiv (-1)^k Q.
\end{align}

Now, write $U$ the set of quadratic residues in $I = [\![1, (p-1)/2]\!]$, $\overline{U}$ its complementary set in $I$, which is the set of quadratic nonresidues in $I$. Then
\begin{align*}
Q &= \left(\frac{p-1}{2}ight)! \
&= \prod _{j \in I} j\
&= \prod_{j \in U} j \cdot \prod_{j \in \overline{U} } j.
\end{align*}
If $j \in \overline{U}$ is a quadratic nonresidue, then $-j$ is a residue, because $-1$ is a nonresidue modulo $p = 4k+3$. Therefore $p-j$ is a quadratic residue, and $p-j \in  J =  [\![ (p+1)/2, p-1]\!]$.

If $m$ is the number of quadratic residues less that $p/2$, there are $(p-1)/ 2 - m$ nonresidues in $I$, thus
\begin{align*}
Q &\equiv (-1)^{\frac{p-1}{2} - m} \prod_{j \in U} j \cdot \prod_{j \in \overline{U} } (p-j) \pmod p.
\end{align*}
The set $R$ of the quadratic residues modulo $p$ in $ [\![1, p-1]\!]$ is the union of the residues in $I =  [\![1, (p-1)/2]\!]$, and the residues in $ J =  [\![ (p+1)/2, p-1]\!]$, all of the form $p-j$, where $j \in \overline{U}$. Therefore
$$\prod_{j \in U} j \cdot \prod_{j \in \overline{U} } (p-j) = \prod_{j \in R} j,$$
where $ \prod\limits_{j \in R} j \equiv 1 \pmod p$ by Problem 16, for $p = 4k+3$. We obtain
\begin{align}
Q \equiv (-1)^{\frac{p-1}{2}} (-1)^m = (-1)^{m+1} \pmod p.
\end{align}
Then (3) and (4) give
$$P = 1\cdot 3\cdot 5 \cdots (p-2) \equiv (-1)^{m+k+1} \pmod p,$$
and (1) gives
$$R= 2 \cdot4 \cdot 6 \cdots (p-1) \equiv (-1)^{m+k} \pmod p.$$
\end{proof}

Exercise 3.1.17* (Find $1\cdot 3 \cdot 5\cdots(p-2)$ modulo $p$)

Answers

Comments

Exercise 3.1.17* (Find $1\cdot 3 \cdot 5\cdots(p-2)$ modulo $p$)

Answers

Comments

Add answer