# Thread: Abstract Algebra: Cyclic Groups and GCD

1. ## Abstract Algebra: Cyclic Groups and GCD

Hail Mathematicians,

Problem:

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

Stuff that might come in handy:

Perhaps some notation will be of assistance.

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

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

What I tried:

($\displaystyle \Rightarrow$). Assume $\displaystyle <[a]> = \mathbb{Z}_n$. Then we have $\displaystyle <[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: $\displaystyle 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 $\displaystyle n$ is odd. Then we have $\displaystyle \frac a2n(n - 1) = nk$ for some $\displaystyle k \in \mathbb{Z}$.

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

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

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

I do know that i want to show that $\displaystyle ak + nl = 1$ for $\displaystyle 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.

($\displaystyle \Leftarrow$) For the converse, assume $\displaystyle (a,n) = 1$. Then $\displaystyle ak + nl = 1$ for some $\displaystyle 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 $\displaystyle <[a]> = \mathbb{Z}_n$ iff $\displaystyle \mbox{gcd}(a,n) = 1$
By your other problem $\displaystyle \left< [a] \right> = \left< [d] \right>$ where $\displaystyle d=\gcd(a,n)$. Say $\displaystyle \left< [d] \right> = \mathbb{Z}_n$ then it means $\displaystyle [1]\in \left< [d] \right>$ and so $\displaystyle [1] = [kd]$ so $\displaystyle 1 = kd + qn$ for some $\displaystyle q$ and therefore it means $\displaystyle d=1$ because otherwise RHS is divisible by $\displaystyle d$ and LHS is not. Try it the other way.

3. Originally Posted by ThePerfectHacker
By your other problem $\displaystyle \left< [a] \right> = \left< [d] \right>$ where $\displaystyle 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.