Exercise 2.8.14 (Order of the inverse modulo $p$)

Question

Suppose that $a$ has order $h \pmod p$, and that $a \overline{a} \equiv 1 \pmod p$. Show that $\overline{a}$ also has order $h$. Suppose that $g$ is a primitive root $\pmod p$, and that $a \equiv g^i \pmod p,\ 0 \leq i < p-1$. Show that $\overline{a} \equiv g^{p-1-i} \pmod p$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Since $a \overline{a} \equiv 1 \pmod p$, we can assure that $a 
ot \equiv 0 \pmod p$. Then, for every positive integer $n$, since $a^n \wedge p = 1$,
\begin{align*}
\overline{a}^n \equiv 1 \pmod p &\iff a^n \overline{a}^n \equiv a^n \pmod p\
&\iff (a\overline{a})^n \equiv a^n \pmod p\
&\iff 1 \equiv a^n \pmod p\
&\iff h \mid n.
\end{align*}
This shows that $\overline{a}^n \equiv 1 \iff  h \mid n$, so that the least positive integer $n$ such that $a^n \equiv 1 \pmod p$ is $h$. So the order of $\overline{a}$ is $h$.

\bigskip
If $a \equiv g^i \pmod p,\ 0 \leq i < p-1$, then 
$$1 \equiv a \overline{a} \equiv g^i \overline{a}.$$
Moreover,
$$ g^i g^{p-1-i} = g^{p-1} \equiv 1 \pmod p,$$
 thus
$$g^i \overline{a} \equiv g^i g^{p-1-i}\pmod p.$$
Since $p \wedge g = 1$, we obtain
$$\overline{a} \equiv g^{p-1-i}\pmod p.$$
\end{proof}

Exercise 2.8.14 (Order of the inverse modulo $p$)

Answers

Comments

Exercise 2.8.14 (Order of the inverse modulo $p$)

Answers

Comments

Add answer