Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
    
I have written a fuller answer now. –  Geoff Robinson Jan 4 '13 at 4:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.