In a cyclic group of order $n$, an element can be written as a $k$th power and $(n,k)$ power in equally many ways? Suppose $\langle x\rangle$ is a cyclic group of order $n$. It is known that any $k$th power can be written as a $d$th power where $d=(n,k)$. 
My question is, why are the number of ways to express an element as a $k$th power equal to the number of ways to express it as a $d$th power? 
Edit: To be clear, I understand that any $k$th power is a $d$th power and vice versa. What I want to ask is that if an element $a$ be expressed as a $k$th power in say $m$ different ways, that is, $a=b^k$ for $m$ distinct $b$, then why does $a=c^d$ for $m$ distinct $c$?
This question was inspired by an answer in the thread Same number of solutions to $ax^m+by^n\equiv c\pmod{p}$ and $ax^{m'}+by^{n'}\equiv c\pmod{p}$. but I felt it was a useful enough fact to warrant its own post.
 A: Since $d = rn+sk$ for integers $r$ and $s,$ every expression as a $d$-th power can be rewritten as a $k$-th power since $y^{rn} = 1$ for all $ y \in \langle x \rangle.$ On the other hand, since $d$ divides $k,$ every expression as a $k$-th power can be rewritten as a $d$-th power.
Answer expanded in view of questions in comments. Set $X = \langle x \rangle,$ and write $k = ed$ for some integer $d.$
Note that $y \to y^{e}$ is a bijection from the set of $d$-th powers in $X$ onto the set of $k$-th powers in $X.$ Surjectivity is clear, while if we have $v^{k} = w^{k},$ then we have $u^{d} = u^{rn+sk} = u^{sk} = v^{sk} = v^{rn+sk} = v^{d},$ showing both injectivity, and that $u \to u^{s}$ is the inverse map back from the set of $k$-th powers to the set of $d$-th powers.
In particular, if $y^{k} = 1,$ then $y^{d} = y^{sk} = 1.$ Now $y \to y^{k}$ is a homomorphism from $X$ to $X$ (but need not be surjective). By the discussion above, its kernel is the set of solutions in $X$ of $y^{d} = 1.$ There are $d$ such solutions, since $d$ divides $n$ and $X$ is cyclic of order $n.$
Now every $d$-th power in $X$ is the $d$-th power of exactly $d$ different elements. On the other hand, if $u^{k} = v^{k},$ then we have $(uv^{-1})^{k} = 1,$ so that $(uv^{-1})^{d}= 1,$ and there are just $d$ possibilities for $uv^{-1}.$
Hence every $k$-th power is the $k$-th power of exactly $d$ different elements.
