Exercise 2.8.22 (Another proof of Wilson's congruence)

Question

Let $g$ be a primitive root $\pmod p$. Show that $(p-1)! \equiv g\cdot g^2\cdot \cdots \cdot g^{p-1} \equiv g^{p(p-1)/2}\pmod p$. Use this to give another proof of Wilson's congruence (Theorem 2.11).

Richard Ganaye · Accepted Answer

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

Notation: Here $\overline{a} \in \Z/p\Z$ denotes the class of $a \in \Z$.
\begin{proof} 
Since $\overline{g}$ is a generator of $(\Z/p\Z)^	imes$, the map
$$\varphi
\left\{
\begin{array}{ccl}
[\![0, p - 1[\![ &	o & (\Z/p\Z)^	imes\
k & \mapsto &\overline{g}^k
\end{array}
ight.
$$
is bijective, so that, using $\overline{g}^{p-1} = 1$,
$$
\{\overline{g},\overline{g}^2,\ldots,\overline{g}^{p-2}, \overline{g}^{p-1}\} = \{\overline{1}, \overline{g},\overline{g}^2,\ldots,\overline{g}^{p-2}\} = \{\overline{1}, \overline{2},\ldots,\overline{p-1}\} = (\Z/p\Z)^	imes.
$$
Therefore
$$\prod_{j=1}^{p-1} \overline{g}^j= \prod_{k = 1}^{p-1} \overline{k} = \overline{(p-1)!}.$$
This shows that
$$(p-1) ! \equiv \prod_{j=1}^{p-1} {g}^j = g \cdot g^2\cdot \cdots \cdot g^{p-1} \pmod p.$$

Therefore, using $g^{(p-1)/2} \equiv -1\pmod p$ (see Problem 15),
\begin{align*}
(p-1)! &\equiv g^{\sum_{j=1}^{p-1} j}\
&\equiv g^{p(p-1)/2}\
&\equiv \left[g^{(p-1)/2}ight]^p\
&\equiv (-1)^p = -1 \pmod p.\
\end{align*}
This gives the Wilson's congruence $(p-1)! \equiv - 1 \pmod p$.
\end{proof}

Exercise 2.8.22 (Another proof of Wilson's congruence)

Answers

Comments

Exercise 2.8.22 (Another proof of Wilson's congruence)

Answers

Comments

Add answer