# Homework Help: Question on cyclic groups

1. Jan 22, 2012

### Flying_Goat

1. The problem statement, all variables and given/known data
Let $G$ be a cyclic group of order $n$ and let $k$ be an integer relatively prime to $n$. Prove that the map $x\mapsto x^k$ is sujective.

2. Relevant equations

3. The attempt at a solution
I am trying to prove the contrapositon but I am not sure about one thing: If the map is not surjective, does it necessarily mean that there exists distinct $i,j \in \{1,...n\}$ such that $(x^i)^k=(x^j)^k$? If so how would you prove it?

Anyway here is my proof:

Suppose that the map is not surjective. Then there exists distinct $i,j \in \{1,...n\}$ such that $(x^i)^k=(x^j)^k$. Without loss of generality suppose $i>j$. Using the cancellation laws we get $x^{(i-j)k}=1$. Since $|x|=n$, it follows that $n|(i-j)k$ (By another proposition). If $gcd(n,k)=1$ then $n|(i-j)$, a contradiction since $(i-j) < n$. Hence we must have $gcd(n,k) \not= 1$ and so $k$ is not relatively prime to $n$. Therefore by contraposition, if $k$ is relatively prime to $n$ then $x\mapsto x^k$ is surjective.

Quite often I find it hard to check whether a proof has flaws in it. How can I improve on checking for flaws in a proof?

Any help would be appreciated.

2. Jan 22, 2012

### Dick

Your proof looks fine to me. If your group is cyclic and x is a generator then your group is G={x^0,x^1,...x^(n-1)}. So, yes, if x->x^k is not surjective then two of those elements must map to the same thing. Hence (x^i)^k=(x^j)^k for some i and j less than n. Sometimes putting real numbers in for n and k helps to check, e.g. put n=6. Show the map is surjective if k=5 and not surjective if k=4 by writing all of the elements out. It should give you a feeling for what's going on if the proof itself isn't giving you that.

3. Jan 23, 2012