# Index relation between two primitive roots

Let n be a positive integer, and x an integer such that gcd(n, x)=1. Suppose g and h are primitive roots mod n. Show that:

$ind_{h}(x) = ind_{h}(g) \cdot ind_{g}(x) (mod {\phi}(n))$

I've been staring at it for about an hour now. I know I can rewrite $ind_{h}(x)$ as $h^{ind_{h}(x)}=x$. But rewriting this in this way leads to $x=gx(mod {\phi}(n))$. I cannot find a way to remove the g. It is a primitive root, so perhaps I can apply Fermat's little theorem in some fashion. The RHS of the equation has a chain rule feel to me, but I've been staring at it for so long I cannot put anything together. Can someone offer perhaps a hint on the matter.

In case: $ind_{h}(x)$ here is used to denote the index of x to the base h

The approach you began is correct. Let $L=\operatorname{ind}_h(x)$ and let $R=\operatorname{ind}_h(g)\operatorname{ind}_g(x)$. To prove the result it is enough to prove that $h^L\equiv h^R\pmod{n}$.
It is clear that $h^L\equiv x\pmod{n}$.
For $h^R$, note that it is equal to $(h^{\operatorname{ind}_h(g)})^{\operatorname{ind}_g(x)}$. Since $h^{\operatorname{ind}_h(g)}\equiv g\pmod{n}$, the result follows.
• Is it true that $\operatorname{ind}_hg$ is coprime with $\varphi(n)$? – ZFR Oct 8 '16 at 20:51