Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$. 
Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1  \pmod n$, where $n$ has a primitive root.

I have proven the following theorem myself:

However, I can't follow the steps in the "Conversely"-part below. I see that $r$ is an primitive root modulo $n$ and $r^{(ind_r a)} \equiv a \pmod n$. 
But why does $\gcd(k, \phi(n)) \mid (ind_r a)$ imply that there are $\gcd(k, \phi(n))$ (in total) solutions to $k (ind_r x) \equiv (ind_r a) \pmod{\phi(n)}$ ? I see that theorem 2.77 is related to this linear congruence, but I don't see how the solutions come into play. 
Also why are solutions to $k (ind_r x) \equiv (ind_r a) \pmod{\phi(n)}$ also solutions to $x^k \equiv a \pmod n$ ?

 A: Let me try to answer your question by giving what I hope is a clear proof of your proposition. Assume that $n$ has a primitive root, and that $k$ is arbitrary but $a$ is relatively prime to $n$ and we seek solutions $x$, also relatively prime to $n$, to the congruence
$$x^k \equiv a \pmod n.$$ The number of integers relatively prime to $n$ is $\phi(n)$ and they form a group under multiplication modulo $n$. This group is assumed to by cyclic, generated by a primitive root which I denote $g$. I also set $m=\phi(n)$ to simplify notation.
 Then if $a=g^l$ the problem is to find integer $t$ such that 
$$(g^t)^k \equiv g^l \pmod n$$ this means 
$$g^{kt-l}\equiv 1 \pmod n$$ and this is equivalent to $m |kt-l$.
So we essentially have to solve the problem of finding all solutions $t$ to 
$$kt\equiv l \pmod m$$ clearly if this has a solution then $(k,m) | l$. 
So now conversely, assume that  $(k,m) | l$, then we have a congruence
$$\frac{k}{(k,m)}t\equiv \frac{l}{(k,m)}\pmod{\frac{m}{(k,m)}}$$ and this has a solution since $\frac{k}{(k,m)}$ and $\frac{m}{(k,m)}$ are relatively prime. This solution will also solve the congruence modulo $m$.
It remains to find the number of distinct solutions modulo $m$.
So assume 
$$kt\equiv l \pmod m$$
and $$ks\equiv l \pmod m$$ thus, 
$k(t-s)\equiv 0 \pmod m$ and this implies that $\frac{m}{(k,m)}|t-s$.
So consider 
$$t+\alpha \frac{m}{(k,m)} \ \ \ \text{for}\ \ \alpha=0,1,\ldots ,(k,m)-1$$
$$k\left(t+\alpha \frac{m}{(k,m)} \right)=kt+\alpha \frac{k}{(k,m)}m \equiv kt \equiv l \pmod m$$
So these represent all $(k,m)$ distinct modulo $m$ solutions corresponding to 
$(k,m)$ distinct modulo $n$ solutions $g^t$ of the original question.
A: Let $g = \gcd(k,φ(n))$ and $k = gm$ and $φ(n) = gd$
If $k(ind_r x) \equiv ind_r a \pmod{φ(n)}$:
  $x^k \equiv r^{k(ind_r x)} \equiv r^{ind_r a} \equiv a \pmod{n}$  [answering your 2nd question]
  $gm(ind_r x) + p (gd) = ind_r a$ for some integer $p$
  Thus $ind_r a = q g$ for some integer $q$
  Thus $m(ind_r x) + p d = q$
  Thus $m(ind_r x) \equiv q \pmod{d}$
  Thus $ind_r x \equiv q m^{-1} \pmod{d}$ because $\gcd(m,d) = 1$
  [Now we simply work backwards to check that the final equation above is equivalent to the original.]
  Therefore there are at most $g$ solutions for $ind_r x$ in the range $[0..gd-1]$
  Let $s \in [0..d-1]$ such that $s \equiv q m^{-1} \pmod{d}$
  Let $S = \{ s + d t : t \in [0..g-1] \} \subseteq [0..gd-1]$
  For any integer $t \in [0..g-1]$:
    If $ind_r x = s + d t$:
      $m(ind_r x) \equiv ms \equiv q \pmod{d}$
      Thus $k(ind_r x) \equiv ind_r a \pmod{gd}$
  Therefore $S$ is a set of $g$ solutions for $ind_r x$
  Therefore there are exactly $g$ solutions for $ind_r x$ in the range $[0..gd-1]$
A: The theorem is false, so one shouldn't be able to prove it. Take $n=8$, so $\phi(n)=4$, and $a=3$, $k=2$. Then $x^k\equiv a\pmod n$ becomes $x^2\equiv3\pmod8$ which has no solution. However $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1  \pmod n$ becomes $3^{4/2}=3^2\equiv1\pmod8$, which is true.
