Exercise 4.9

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

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

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

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

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

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

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

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

Show that the product of all the primitive roots modulo $p$ is congruent to $(-1)^{\phi(p-1)}$ modulo $p$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow} \def\gcro{\mbox{[\hspace{-.15em}[}} \def\dcro{\mbox{]\hspace{-.15em}]}} ewcommand{\D}{\mathrm{d}} ewcommand{\Q}{\mathbb{Q}} ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} ewcommand{\C}{\mathbb{C}} ewcommand{\F}{\mathbb{F}} ewcommand{ e}{\,\mathrm{Re}\,} ewcommand{\ord}{\mathrm{ord}} ewcommand{ }{\mathrm{N}} ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}} \begin{proof} Here we suppose $p$ prime, $p>2$. Let $g$ be a primitive root modulo $p$. $U(\Z/p\Z)$ is cyclic, generated by $\overline{g}$: $$U(\Z/p\Z) = \{\overline{1},\overline{g}, \overline{g}^2, \ldots,\overline{g}^{p-2}\},\qquad \overline{g}^{p-1} = \overline{1}.$$ $\overline{g}^k$ is a primitive element iff $k \wedge (p-1) = 1$, therefore the product of primitive elements in $U(\Z/p\Z)$ is $$\overline{P} = \prod_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}} \overline{g}^k.$$ thus $\overline{P} = \overline{g}^S$, where $S = \sum\limits_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}} k$. From Ex. 2.22, we know that for $n\geq 2$, $$\sum_{\overset{k\wedge n = 1}{ 1\leq k < n}} k = \frac{1}{2} n \phi(n).$$ So $S = \sum\limits_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}} k = \frac{1}{2} (p-1) \phi(p-1)$. As $p>2$, $p-1$ is even. $(\overline{g}^{(p-1)/2})^2 = \overline{g}^{p-1} = \overline{1}$, and $\overline{g}^{(p-1)/2} e \overline{1}$. As $\Z/p\Z$ is a field, $\overline{g}^{(p-1)/2} = -\overline{1}$. Thus $\overline{P} = (-\overline{1})^{\phi(p-1)}$, and the product $P$ of all the primitive roots modulo $p$ is such that $$P \equiv (-1)^{\phi(p-1)} \pmod p.$$ \end{proof}

Exercise 4.9

Answers

Comments

Exercise 4.9

Answers

Comments

Add answer