1. Cyclic Groups

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.

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

I think you were on the right path but somewhere you decided to do life harder to yourself: let $\displaystyle b = x^m$ be any element in G, so:

$\displaystyle b = x^m=x^{m\cdot 1}=x^{mar+mbn}=(x^r)^{ma}\,(x^n)^{mb}=(x^r)^{ma}\c dot 1\in<x^r>$

And thus any element in G is a power of x^r.

Tonio

3. Thanks very much. Do you have any suggestions for proof in the other direction? I'm not even sure where to begin

4. Originally Posted by slevvio
Thanks very much. Do you have any suggestions for proof in the other direction? I'm not even sure where to begin

We know that $\displaystyle (r,n)=1\Longleftrightarrow rk+ny = 1\,,\,\;k\,,\,y\in \mathbb{Z}$. So, if <x^r> = x, then ord(x^r)= n; OTOH:

$\displaystyle \exists k\in \mathbb{Z}\,\,s.t. (x^r)^k=x\Longrightarrow x^{rk-1}=1\Longrightarrow n\mid rk-1\Longrightarrow\,...$

Tonio

5. proof

Let $\displaystyle d = gcd ( r, n )$

Then $\displaystyle d | n$ and $\displaystyle d | r$

So $\displaystyle (x^r)^{\frac{n}{d}} = (x^n)^{\frac{r}{d} } = 1$

So $\displaystyle |x^r| \le \frac{n}{d}$

But we know $\displaystyle |x^r| = |G|= n$ by assumption.

Hence $\displaystyle n \le \frac{n}{d} \implies d \le 1$

But $\displaystyle d \ge 1$ by definition of greatest common divisor, hence $\displaystyle d = 1$.

Ta-dah!

Thanks for the help everyone !