# 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.

-
Because $x\mapsto x^{k/(k,n)}$ is an automorphism since $(k/(k,n),n)=(k,n)/(k,n)=1$, putting the $(k,n)$th powers and $k$th powers in bijective correspondence. – anon Jan 3 '13 at 21:54
@anon How did you get the equality $(k/(k,n),n)=(k,n)/(k,n)$? Thanks. – Dedede Jan 3 '13 at 22:03
Actually I shouldn't have phrased it that way (I was mentally using an erroneous general formula), but wlog we can assume $k\le n$ in which case $k/(k,n)$ and $n$ are indeed coprime. – anon Jan 3 '13 at 22:12
@anon What if $k=4$ and $n=6$? Then $k/(k,n)=4/2=2$, so $k/(k,n)$ and $n$ aren't coprime. – Dedede Jan 3 '13 at 22:15
Well then I am really off my rocker tonight! – anon Jan 4 '13 at 2:31

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.
Thanks, I get that each $k$th power can be written as a $d$th power and vice versa for just that reason, but how does that show that there are necessarily an equal number of representations for an element in each power? – Dedede Jan 3 '13 at 22:09
Sorry, but I don't see how that implies the number of $k$-power and $d$-power representations of $z$ are the same. I get that if $z=y^d$, then $z=y^{sk}$, but why do you take $y_1^s$ and $y_2^s$, and set them to $u_1$ and $u_2$? What is the goal of showing that $y_1^d=y_2^d$? – Dedede Jan 3 '13 at 23:11