An elaboration of how an index formula comes from another formula.

Question

A theorem is given below (in which the book said that it is used in justifying how the index formula in question came) :

And this picture contains the index formula that the author said that it comes from (a) & (b) of thm.8.11:

Could anyone explain for me how this congruence $k \operatorname{ind}x \equiv\operatorname{ind}a \pmod{\phi (n)},$ comes from $(a)$ & $(b)$ of thm.8.11?

Thanks!

Answer 1

$\newcommand{\ind}{\operatorname{ind}}$

Recall the theorem:

If the integer $r$ has order $k$ modulo $n$, then $r^i \equiv r^j\pmod n$ if and only if $i \equiv j \pmod k$.$\tag{1}$

Now let $r$ be a primitive root of $n$. Then $$\begin{align*}x^k &\equiv a \pmod n\\\iff r^{\ind x^k}&\equiv r^{\ind a}\pmod n\\\iff\ind x^k&\equiv \ind a\pmod{\phi(n)}&&\qquad(\text{by $(1)$})\\\iff k\, \ind x&\equiv\ind a \pmod{\phi(n)}&&\qquad(\text{by $(b)$}).\end{align*}$$

Answer 2

$x^k \equiv a $ (mod n)

By definition we have $r ^ {ind(a)} = a$ (mod n) and (Euler) $r ^{\phi(n)} \equiv 1$ (mod n). So we get

$r ^ {ind(x^k)} \equiv r^{ind (a)} r^{\phi(n)} = r^{ind(a)+\phi(n)}$ (mod n)

Thus (I'm not 100% sure about this part. The inverse direction is clear, though)

$ind(x^k) \equiv ind(a)$ (mod $\phi(n)$)

$\Leftrightarrow k$ $ind(x) \equiv ind(a)$ (mod $\phi (n)$)