# Thread: Abstract Algebra: Cyclic Groups and GCD 2

1. ## Abstract Algebra: Cyclic Groups and GCD 2

Hi all,

My brain is fried by now, I'm not sure where to go with this homework problem.

Problem:

Prove that $<[a]> = <[b]>$ in $\mathbb{Z}_n$ iff $gcd(a,n) = gcd(b,n).$ (See problem 15.26).

Things that might come in handy:

Here is problem 15.26:

Prove that if $gcd(a,n) = d$, then $<[a]> = <[d]>$ in $\mathbb{Z}_n$

For notation, see here

There's a theorem, I don't know how useful it would be in this case.

Theorem: Let $T_1$ and $T_2$ be subsets of a group $G$. Then

$ = $ iff $T_1 \subseteq $ and $T_2 \subseteq $

I will supply any other useful information upon request.

What I tried:

Like i said, my brain is fried.

I'm not sure how to apply the $<[a]> = <[b]>$ part, but i know that, given that that's true, i want to show that $ak + nl = bp + nr$, for $k,l,p,r \in \mathbb{Z}$

Also lost for the converse.

Thanks guys and gals

2. Originally Posted by Jhevon

Prove that $<[a]> = <[b]>$ in $\mathbb{Z}_n$ iff $gcd(a,n) = gcd(b,n).$ (See problem 15.26).
Given positive integer $a$:
$\left< [a] \right> = \left< [d] \right>$ where $d=\gcd(a,n)$.
Now since $\gcd(b,n) = d$ it means $\left< [b] \right> = \left< [d] \right>$.
Thus, $\left< [a] \right> = \left< [b] \right>$.

So that means we need to prove $\left< [a] \right> = \left< [d] \right>$ when $\gcd(a,n) = d$. Note $[a]\in \left< [d] \right>$ because $d|a$, this means $\left< [a] \right> \subseteq \left< [d] \right>$. Note there exist $x,y\in \mathbb{Z}$ so that $ax+ny=d$. Thus, $[d] = [ax+ny] = [ax]$, so $[d] \in \left< [a] \right>$ which means $\left< [d] \right> = \left< [a] \right>$.

3. Originally Posted by ThePerfectHacker
Given positive integer $a$:
$\left< [a] \right> = \left< [d] \right>$ where $d=\gcd(a,n)$.
Now since $\gcd(b,n) = d$ it means $\left< [b] \right> = \left< [d] \right>$.
Thus, $\left< [a] \right> = \left< [b] \right>$.

So that means we need to prove $\left< [a] \right> = \left< [d] \right>$ when $\gcd(a,n) = d$. Note $[a]\in \left< [d] \right>$ because $d|a$, this means $\left< [a] \right> \subseteq \left< [d] \right>$. Note there exist $x,y\in \mathbb{Z}$ so that $ax+ny=d$. Thus, $[d] = [ax+ny] = [ax]$, so $[d] \in \left< [a] \right>$ which means $\left< [d] \right> = \left< [a] \right>$.
Using problem 26, it was actually easy proving this direction. it was really the other direction i was interested in.

i want to show that $<[a]> = <[b]> \implies gcd(a,n) = gcd(b,n)$

okay, so if i assume $<[a]> = <[b]>$, then $[a] = [kb]$ for some $k \in \mathbb{Z}$. So, $a \equiv kb ~(\mbox{mod }n) \Longleftrightarrow a - kb = ln$ for some $l \in \mathbb{Z}$. Thus, $a = kb + ln$

Similarly, I can get $b = ma + rn$ for $m,r \in \mathbb{Z}$.

What now?