# Thread: Abstract Algebra: Cyclic Groups and GCD

1. ## Abstract Algebra: Cyclic Groups and GCD

Hail Mathematicians,

Problem:

Prove that $<[a]> = \mathbb{Z}_n$ iff $\mbox{gcd}(a,n) = 1$

Stuff that might come in handy:

Perhaps some notation will be of assistance.

Let $G$ be a group and $a \in G$. We denote the subgroup generated by $a$ as $$

For anything else, Ask, and it shall be given unto you.

What I tried:

( $\Rightarrow$). Assume $<[a]> = \mathbb{Z}_n$. Then we have $<[a]> = \{ [0],[a],[a]^2,[a]^3, \cdots , [a]^{n - 1}\} = \{ [0], [a], [2a], \cdots [(n - 1)a] \}$ (this is right, right?)

By this problem: $0 + a + 2a + \cdots + (n - 1)a = \frac a2n(n - 1) = \left \{ \begin{array}{lr} 0~\mbox{mod }n & \mbox{ if }n \mbox{ is odd} \\ & \\ \frac n2~\mbox{mod }n & \mbox{ if }n \mbox{ is even } \end{array} \right.$

Say $n$ is odd. Then we have $\frac a2n(n - 1) = nk$ for some $k \in \mathbb{Z}$.

and i don't know where to go from there.

Say $n$ is even. Then $\frac a2n(n - 1) - \frac n2 = mn$ for some $m \in \mathbb{Z}$.

and i don't know where to go from there.

I do know that i want to show that $ak + nl = 1$ for $k,l \in \mathbb{Z}$. Furthermore, I have to make sure 1 is the gcd by showing that 1|a, 1|n and if there is some b such that b|a and b|n then b|1.

( $\Leftarrow$) For the converse, assume $(a,n) = 1$. Then $ak + nl = 1$ for some $k,l \in \mathbb{Z}$.

and i don't know where to go from there.

Help

Thanks guys and gals

2. Originally Posted by Jhevon
Hail Mathematicians,

Problem:

Prove that $<[a]> = \mathbb{Z}_n$ iff $\mbox{gcd}(a,n) = 1$
By your other problem $\left< [a] \right> = \left< [d] \right>$ where $d=\gcd(a,n)$. Say $\left< [d] \right> = \mathbb{Z}_n$ then it means $[1]\in \left< [d] \right>$ and so $[1] = [kd]$ so $1 = kd + qn$ for some $q$ and therefore it means $d=1$ because otherwise RHS is divisible by $d$ and LHS is not. Try it the other way.

3. Originally Posted by ThePerfectHacker
By your other problem $\left< [a] \right> = \left< [d] \right>$ where $d=\gcd(a,n)$. ...
what problem are you referring to here? if you are referring to 15.26 from one of my other posts, we can't use that.