1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it true that $\operatorname{ind}_hg$ is coprime with $\varphi(n)$? $\endgroup$ – ZFR Oct 8 '16 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.