1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question on cyclic groups

  1. Jan 22, 2012 #1
    1. The problem statement, all variables and given/known data
    Let [itex]G[/itex] be a cyclic group of order [itex]n[/itex] and let [itex]k[/itex] be an integer relatively prime to [itex]n[/itex]. Prove that the map [itex]x\mapsto x^k[/itex] 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 [itex]i,j \in \{1,...n\}[/itex] such that [itex](x^i)^k=(x^j)^k[/itex]? If so how would you prove it?

    Anyway here is my proof:

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


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Jan 23, 2012 #3
    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?
  5. Jan 23, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    Sure. If x is in G, then x^k is in G. Groups are closed under the operation.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook