Prove that if $g$ and $h$ are primitive roots modulo $m$ so $\text{ind}_g (h)$ is the inverse of $\text{ind}_h (g)$ modulo $\phi(m)$

My attempt:

I need to prove that $\text{ind}_h (g)\cdot \text{ind}_g (h)\equiv 1 \pmod{\phi (m)}$

Because $g$ and $h$ are primitive roots modulo $m$

$$\text{ord}_m (g)=\text{ord}_m (h)=\phi(m)$$

$$\Longrightarrow g^{\phi(m)}\equiv h^{\phi(m)}$$

$$\Longrightarrow h=g$$

$$\Longrightarrow \text{ind}_h (h)\cdot \text{ind}_h (h)=1$$

I am not sure at all about what I did


1 Answer 1


Let $a=\text{ind}_g(h)$ and $b=\text{ind}_h(g)$. Then $h\equiv g^a\pmod{m}$ and $g\equiv h^b\pmod{m}$. So $h\equiv (h^b)^a\equiv h^{ab}\pmod{m}$. It follows that $ab\equiv 1\pmod{\varphi(m)}$.

Remarks: $1.$ The solution proposed in the OP does not work. It is true that $g^{\varphi(m)}\equiv h^{\varphi(m)}\pmod{m}$, they are both congruent to $1$. But from this one cannot conclude that $g=h$.

$2.$ Note that the relationship we have established is analogous to the relationship between $\log_x y$ and $\log_y x$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .