Originally Posted by

**slevvio** Hey everyone I was wondering if anybody could help me with this problem.

Let G = <x> where x has order n and let r denote a positive integer. Prove that $\displaystyle x^r $ generates G if and only if gcd(r,n) = 1, i.e. r and n are coprime.

I guess I am trying to prove the statement $\displaystyle |x^r | = n \iff gcd (r,n) = 1 $.

When I try to do this however I just get a strange result... I would appreciate any guidance with this to see where I have gone wrong or what I can do to solve it.

Proof (<=)

$\displaystyle gcd (r,n)=1 \implies \exists a,b \in \mathbb{Z} $ such that $\displaystyle ar + bn = 1 \implies ar = 1 - bn $

So $\displaystyle x = x ^{ar+bn} \implies x^r = x^{rar +rbn} = x^{rar}x^{rbn}=x^{rar}(x^n)^{rb} = x^{rar}1^{rb} = x^{rar} $ since |x| = n.

Also $\displaystyle x^{ar} = x^{1-bn} = x x^{-bn} = x (x^n)^{-b} = x 1 ^{-b} = x$ since |x| = n.

Hence $\displaystyle x^r = x^{rar} = x^r x^{ar} = x ^{ra} x^r =x^r x = x x^r $ giving $\displaystyle x = 1 $ which of course means $\displaystyle |x^r| = |x| = n = 1 $.

Is this right, have I done something wrong?? Any help would be appreciated.