The number of solutions to $x^k = a$ over $G$ a finite cyclic group is $\gcd(k,|G|)$ Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a \Leftrightarrow  a^\frac{n}{\gcd(k,n)} = e$.
I wish to show that in case there is a solution $x_0\in G$, such that $x_0^k=a$, then there are exactly $\gcd(k,n)$ solutions for $x^k =a$.
Well, I worked out that $a$ is a $k'th$ root in $G$ $\Rightarrow$ $a$ is a $\gcd(k,n)'th$ root in $G$.
An other observation is that there are exactly $\frac{n}{\gcd(k,n)}$ elements in $G$ which are roots of order $k$, cause in case $d||G|$, there are exactly $d$ solution for $x^d=e$.
 A: Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer. 
Since $x_0^k=a$, $(g^i)^k=a\implies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).  
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^m\implies g^{ik}*(g^m)^{-1}=e\implies g^{ik-m}=e\implies \operatorname{ord}(g)|(ik-m)$.   
So suppose for some $y\in G$ (that may or may not be equal to $x_0$), we have $y^k=a$.   
We can write $y$ as $g^j$, where $0\leq j< n$ so that $g^{jk}=a$.  
This means (referring back to the "As a result..." line):
$$n|(ik-jk)\implies n|k(i-j)\implies\frac{n}{g.c.d(n,k)}\Big|\frac{k}{g.c.d(n,k)}(i-j)$$ 
But $\frac{n}{g.c.d(n,k)}$ and $\frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so  
$\frac{n}{g.c.d(n,k)}\Big|(i-j)$. 
On the other hand, suppose we are given some $0\leq j< n$ such that $\frac{n}{g.c.d(n,k)}\Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(\frac{n}{g.c.d(n,k)}s)k}=(g^n)^{s\frac{k}{g.c.d(n,k)}}=e^{s\frac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}\implies (g^j)^k=a$$ 
(above we have used $s=\frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $\frac{n}{g.c.d(n,k)}\Big|(i-j)$. This means we can consider all distinct values of $j\operatorname{mod}n$ such that $j=i-s\frac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$. 
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $\operatorname{mod}n$.  
This is equivalent to saying $g.c.d(n,k)j\equiv g.c.d(n,k)i\;\operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.  
Lucky for us, we know that, in general, $ax\equiv b\operatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)  
So the equation $g.c.d(n,k)j\equiv g.c.d(n,k)i\;\operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.  
(please comment or edit for any corrections)
