# Find a generator of the intersection of two cyclic subgroups, $\langle a^m\rangle\cap\langle a^n\rangle$ [duplicate]

Let $a$ be an element in a group $G$. What is a generator for the subgroup $H = G_1 \cap G_2$ where $G_1, G_2$ are the groups generated by $a^m, a^n$, respectively?

Please can someone check my proof that I posted below?

I had actually already solved the question! I was just wondering if anybody could write out a fully rigorous proof so I can check if mine works. Basically, the problem is easy if the order of $a$ is infinite, but in the case where the order of $a$ is finite, a bit more care needs to be taken.

Anyway, here's how I did it:

We will prove that $⟨a^{lcm(m,n)}⟩ = H$.

Firstly, note that $a^{lcm(m,n)} \in G_1, G_2$ so $⟨a^{lcm(m,n)}⟩ \subseteq H$.

Now assume $a^k \in H$. If $a$ has infinite order, $m|k$ and $n|k$, implying that $lcm(m,n)|k$, so $a^k \in ⟨a^{lcm(m,n)}⟩$. If $a$ has finite order, say $r$, then there exists an integer $x$ such that $r|k-mx$ as $a^k \in G_1$. Thus $gcd(m,r) | k$. Similarly $gcd(n,r) | k$. So $lcm(gcd(m,r), gcd(n,r))|k$. It is not hard to show that this big lcm expression equals $gcd(lcm(m,n), r)$, so $gcd(lcm(m,n), r) | k$. Now let $lcm(m,n)=dp, r=dq$ for coprime $p,q$. Then $d|k$ so write $k=de$ for an integer $e$.

We would like to find an integer $s$ such that $r|k-slcm(m,n)$, but this is equivalent to $dq|de-sdp$ iff $q|e-sp$, and such $s$ can be found as $p,q$ are coprime!

Hence $a^k \in ⟨a^{lcm(m,n)}⟩$ and we are done.

Please let me know whether or not this proof is correct, and have I complicated things?

• Do you have a guess? Do you need help understanding the question? – Zev Chonoles Jul 7 '15 at 15:35
• If $m=2,n=3$, what is the smallest (positive) power of $a$ that is in both $G_1$ and $G_2$? How about if $m=4,n=6$? Try it out, make a guess, then prove it. – Arthur Jul 7 '15 at 15:42

Hint: note $H, G_1$ and $G_2$ are all subgroups of $\langle a \rangle$ (a cyclic group). If $H = \langle a^k\rangle$, what could $k$ possibly be?

So $G_1$ contains elements of $a$ to the power of a multiple of $m$, and similarly for $G_2$ with multiple of $n$. Thus if $a^i$ is in both $G_1$ and $G_2$, then $i$ must divide multiples of both $m$ and $n$. Since we are looking for multiples of $m$ which equal multiples of $n$ and thus belong to both groups, we are looking for $common$ multiples.

Thus the intersection of $G_1$ and $G_2$ consists of $a$ to the power of a common multiple of $m$ and $n$. I think you can see where this is going.

• MathJax is for math, whereas markdown is for text. Typing $common$ means "the product of $c$, $o$, $m$, $m$, $o$, and $n$". To make italicized text, use asterisks, e.g. *common*. – Zev Chonoles Jul 7 '15 at 16:07

I had actually already solved the question! I was just wondering if anybody could write out a fully rigorous proof so I can check if mine works. Basically, the problem is easy if the order of $a$ is infinite, but in the case where the order of $a$ is finite, a bit more care needs to be taken.

Anyway, here's how I did it:

We will prove that $⟨a^{lcm(m,n)}⟩ = H$.

Firstly, note that $a^{lcm(m,n)} \in G_1, G_2$ so $⟨a^{lcm(m,n)}⟩ \subseteq H$.

Now assume $a^k \in H$. If $a$ has infinite order, $m|k$ and $n|k$, implying that $lcm(m,n)|k$, so $a^k \in ⟨a^{lcm(m,n)}⟩$. If $a$ has finite order, say $r$, then there exists an integer $x$ such that $r|k-mx$ as $a^k \in G_1$. Thus $gcd(m,r) | k$. Similarly $gcd(n,r) | k$. So $lcm(gcd(m,r), gcd(n,r))|k$. It is not hard to show that this big lcm expression equals $gcd(lcm(m,n), r)$, so $gcd(lcm(m,n), r) | k$. Now let $lcm(m,n)=dp, r=dq$ for coprime $p,q$. Then $d|k$ so write $k=de$ for an integer $e$.

We would like to find an integer $s$ such that $r|k-slcm(m,n)$, but this is equivalent to $dq|de-sdp$ iff $q|e-sp$, and such $s$ can be found as $p,q$ are coprime!

Hence $a^k \in ⟨a^{lcm(m,n)}⟩$ and we are done.

Please let me know whether or not this proof is correct, and have I complicated things?