Proving the Surjectivity of Maps in Cyclic Groups with Relatively Prime Integers

[Flying_Goat]

Homework Statement

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.

Homework Equations

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.

 

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

 

[Flying_Goat]

Thanks for the reply Dick.

So the image of the map is a subset of G, that is why if the map is not surjective then two elements must map to the same thing. Is that correct?

 

[Dick]

Thanks for the reply Dick.

So the image of the map is a subset of G, that is why if the map is not surjective then two elements must map to the same thing. Is that correct?

Sure. If x is in G, then x^k is in G. Groups are closed under the operation.