# How to show $\langle a^k\rangle\leq \langle a^\ell\rangle\Leftrightarrow \gcd(\ell, n)\mid \gcd(k, n).$?

Consider the cyclic group $G=\langle a\rangle$ where $o(a)=n$ where $o(a)$ means order of $a$. I'd like to show: $$\langle a^k\rangle\leq \langle a^\ell\rangle\Leftrightarrow \gcd(\ell, n)\mid \gcd(k, n).$$

I have already done the implication $(\Rightarrow)$ as follows:

I know $$\displaystyle o(a^k)=\frac{n}{\gcd(k, n)}\quad \textrm{and}\quad \displaystyle o(a^\ell)=\frac{n}{\gcd(\ell, n)}.$$ By Lagrange's theorem if $\langle a^k\rangle\leq \langle a^\ell\rangle$ then $o(a^k)\mid o(a^\ell)$ hence $\gcd(\ell, n)\mid \gcd(k, n)$.

How can I show the opposite implication?

Thanks

• I changed \textrm{gcd} to \gcd. This standard usage will appear unitalicized, but unlike \textrm{gcd}, it automatically results in proper spacing in expressions like $a\gcd(b,c)$. ${}\qquad{}$ – Michael Hardy Oct 25 '14 at 0:00
• Ok, thanks! I didn't know the (obvious) command $\gcd$ =) – PtF Oct 25 '14 at 0:00
Let $\gcd(l,n)=d_1$ and $\gcd(k,n)=d_2$, now $d_1=a_1l+b_1n$ and $d_2=a_2k+b_2n$ for some $a_1,b_1,a_2,b_2 \in \mathbb{Z}$ and we have $d_1|d_2$ so it implies $a_1l+b_1n=t(a_2k+b_2n)$ for some $t \in \mathbb{Z}$ hence $$ta_2k=(a_1l+b_1n-tb_2n)$$ so, $$a^{ta_2k}=a^{(a_1l+b_1n-tb_2n)}=a^{a_1l} \in <a^l>$$ and so $$a^{k-ta_2k}.a^{ta_2k}=a^k \in <a^l>$$ $\hspace{16cm}$$\mathbf{QED}$