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.