# 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 $\displaystyle <[a]> = <[b]>$ in $\displaystyle \mathbb{Z}_n$ iff $\displaystyle gcd(a,n) = gcd(b,n).$ (See problem 15.26).

Things that might come in handy:

Here is problem 15.26:

Prove that if $\displaystyle gcd(a,n) = d$, then $\displaystyle <[a]> = <[d]>$ in $\displaystyle \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 $\displaystyle T_1$ and $\displaystyle T_2$ be subsets of a group $\displaystyle G$. Then

$\displaystyle <T_1> = <T_2>$ iff $\displaystyle T_1 \subseteq <T_2>$ and $\displaystyle T_2 \subseteq <T_1>$

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 $\displaystyle <[a]> = <[b]>$ part, but i know that, given that that's true, i want to show that $\displaystyle ak + nl = bp + nr$, for $\displaystyle k,l,p,r \in \mathbb{Z}$

Also lost for the converse.

Thanks guys and gals

2. Originally Posted by Jhevon

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

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

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

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

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

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

What now?