- #1
Flying_Goat
- 16
- 0
Homework Statement
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.
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 [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.