# Show $\langle a^m \rangle \cap \langle a^n \rangle = \langle a^{\operatorname{lcm}(m, n)}\rangle$

So I want to show that $\langle a^m \rangle \cap \langle a^n \rangle = \langle a^{\operatorname{lcm}(m, n)}\rangle$. My approach to this problem was to show a double containment, i.e. to show that $\langle a^m \rangle \cap \langle a^n \rangle \subseteq \langle a^{\operatorname{lcm}(m, n)}\rangle$ and $\langle a^{\operatorname{lcm}(m, n)}\rangle \subseteq \langle a^m \rangle \cap \langle a^n \rangle$.

I would like to see a full proof for this, specifically $\langle a^m \rangle \cap \langle a^n \rangle \subseteq \langle a^{\operatorname{lcm}(m, n)}\rangle$. (I tried it with the approach of breaking it down into to cases; $a$ has infinite order and $a$ has finite order, the latter of which i would appreciate the most help on.)

My approach to solving the whole problem: (I would appreciate any feedback on anything that is wrong, or a different approach to the proof.)

To show the easier containment, $\langle a^{\operatorname{lcm}(m, n)}\rangle \subseteq \langle a^m \rangle \cap \langle a^n \rangle$, I did the following: Let $l = \operatorname{lcm}(m, n)$. Let $j \in \langle a^l\rangle$, so $j = (a^l)^k = a^{lk}$ for some $k \in \mathbb Z$. Since $l$ is a multiple of $m$ and $n$ by definition, we can say $l = ms = nt$ for some $s, t \in \mathbb Z$. Now $j = a^{kl} = a^{kms} = (a^m)^{ks} \in \langle a^m\rangle$. Similarly, $j = a^{kl} = a^{knt} = (a^n)^{kt} \in \langle a^n\rangle$. Now, since $j \in \langle a^m\rangle$ and $j \in \langle a^n\rangle$, it follows that $j \in \langle a^m \rangle \cap \langle a^n \rangle$. Thus, by definition, $\langle a^{\operatorname{lcm}(m, n)}\rangle \subseteq \langle a^m \rangle \cap \langle a^n \rangle$.

For the second containment, the one which I'm having more problems with, I attempted the following:

Case in which $a$ is infinite: Suppose that $\vert a \vert = \infty$. Let $c \in \langle a^m \rangle \cap \langle a^n \rangle$. Then $c = a^{mx} = a^{ny}$ where $x, y \in \mathbb Z$. It follows that $a^{mx - ny} = e$ and so $mx = ny$ because if $mx > ny$ then the difference would not be zero, and we would have an element that was finite, contradicting our hypothesis. And since $mx = ny$ we know $\operatorname{lcm}(mx, ny) = mx = ny$ and $\operatorname{lcm}(mx, ny)$ is a multiple of $\operatorname{lcm}(m, n)$. Hence $c \in \langle a^{\operatorname{lcm}(m, n)}\rangle$ and thus $\langle a^m \rangle \cap \langle a^n \rangle \subseteq \langle a^{\operatorname{lcm}(m, n)}\rangle$.

Case in which $a$ is finite: I tried starting it out the same as the previous case, but i could never reach my conclusion :(

• Robert:May you show where this problem came from? – Victor Apr 15 '12 at 21:09
• @Victor This problem does not require context to the level of source of the problem. Robert has elaborated enough for us to believe he has worked through this problem a bit and not merely worked his fingers on the ctrl keys. Further, this is not a problem that specialists' skills are required to track. This is a typical problem in a first course in group theory. Regards, – user21436 Apr 15 '12 at 21:12
• The $\gcd$ and $\operatorname{lcm}$ have dual definitions through their universal properties as follows: $$\forall n:\quad\begin{array}{c c}n|\gcd(a,b)\iff n|a~\wedge~n|b \\ a|n~\wedge~b|n\iff\operatorname{lcm}(a,b)|n.\end{array}$$ I saw these in a Bill D answer, and they make arguments for propositions like this pretty slick. – anon Apr 15 '12 at 21:24
• @johnw.: Not quite a repeat; it's a "repeat" only in the case where $a$ is of infinite order, not in the case where it is of finite order. – Arturo Magidin Apr 15 '12 at 21:38
• In fancy terms, the lattice of subgroups of a cyclic group is isomorphic to the lattice of divisors of the order of the group. – lhf Apr 16 '12 at 0:01

$\def\lcm{\mathrm{lcm}}$Let $k$ be the order of $a$, with $k=0$ if $a$ is of infinite order. Note that $x\equiv y \pmod{0}$ is equivalent to $x=y$ (since $0|x-y$ if and only if $x-y=0$). Also, $\mathrm{lcm}(n,0) = \gcd(n,0) = n$.

Consider first the case with $n|k$ and $m|k$.

To show $\langle a^m\rangle\cap\langle a^n\rangle \subseteq \langle a^{\lcm(m,n)}\rangle$, let $x$ lie in the intersection. Then there exist $r,s\in\mathbb{Z}$ such that $x=a^{mr} = a^{ns}$, so $mr\equiv ns\pmod{k}$. Thus, $k|mr-ns$, so $n|mr-ns$ and $m|mr-ns$. Therefore, $n|mr$ and $m|ns$. Since $n|mr$, then $mr$ is a common multiple of $n$ and $m$, hence is a multiple of $\lcm(m,n)$ (similarly with $ns$), so we can find $q$ such that $mr=q\lcm(m,n)$. Thus, $x = a^{mr} = a^{q\lcm(m,n)}\in\langle a^{\lcm(m,n)}\rangle$, as desired.

Now for the general case, note that $\langle a^n\rangle = \langle a^{\gcd(n,k)}\rangle$; thus, we are reduced to showing that $\lcm(n,m) \equiv \lcm(\gcd(n,k),\gcd(m,k))\pmod{k}$. This is true, but you may not have it in your arsenal yet, so here's a proof (that no doubt Bill Dubuque can prove in a much slicker way):

Lemma. $\lcm(\gcd(n,k),\gcd(m,k)) = \gcd(\lcm(n,m),k)$.

Proof. Indeed, $\gcd(n,k)$ and $\gcd(m,k)$ both divide $k$, hence their least common multiple divides $k$; and $\lcm(n,m)$ is a common multiple of $\gcd(n,k)$ and $\gcd(m,k)$, so $\lcm(\gcd(n,k),\gcd(m,k))$ divides $\lcm(n,m)$. Thus, the left hand side divides the right hand side. Conversely, let $p$ be a prime and suppose that $p^a$ is the largest power of $p$ that divides $\gcd(\lcm(n,m),k)$. Then $p^a$ divides both $\lcm(n,m)$ and $k$, but $p^{a+1}$ does not divide at least one of them. Since $p^a$ divides $\lcm(n,m)$, then $p^a$ divides either $n$ or $m$, and we also know $p^a$ divides $k$. Either $p^{a+1}$ does not divide $k$, or it does not divide either $n$ or $m$. Thus, $p^a$ divides either $\gcd(n,k)$ or $\gcd(m,k)$, but $p^{a+1}$ divides neither. Therefore, $p^a$ is the largest power of $p$ that divides $\lcm(\gcd(n,k),\gcd(m,k))$. $\Box$

Now the result follows: note that $\gcd(\lcm(n,m),k) \equiv \lcm(n,m)\pmod{k}$ (express $\gcd(\lcm(m,n),k)$ as a linear combination of $\lcm(m,,n)$ and $k$), so we are done.

• It took me a while to work it through. I followed it for the most part, however I don't think I would have figured that out myself :( Thank You though! – Robert Cardona Apr 15 '12 at 22:40
• @Robert: The difficulty is when you are not picking the "distinguished" generators for $\langle a^n\rangle$ and $\langle a^m\rangle$ (with $n|k$ and $m|k$); as you can see, the case where $n|k$ and $m|k$ follows pretty much like it does in the infinite case. – Arturo Magidin Apr 15 '12 at 22:54
• To Arturo Magidin: i have confusing about the difference between general case and the case where n|k and m|k, please help. – Victor Apr 16 '12 at 3:37
• What is confusing about the difference? In one of them we assume $n|k$ and $m|k$; in the other we don't. For example, if $a$ has order $16$, we could have $n=6$ and $m=8$. What is it you are confused about, really? – Arturo Magidin Apr 16 '12 at 3:41

Note $\$ The equality in the lemma in Arturo's answer - that gcd distributes over lcm - can be derived simply via lcm, gcd laws. Rewriting lcms to gcds using $\rm\:lcm(a,b) =\: ab/(a,b)\:$ and clearing denominators, we deduce that the equality is equivalent to

$$\rm (k,m,n)\:(km,kn,mn)\ =\ (k,m)\:(k,n)\:(m,n)$$

true since both $\rm = (kkm,kkn,kmn,kmm,knn,mmn,mnn)\:$ by the distributive law. $\$ QED
For further details see this answer.

Dually, one could rewrite gcds to lcms, reducing it to the lcm dual of the above. And, of course, the dual identity is true: lcm distributes over gcd. These are well-known identities that come to the fore in the lattice viewpoint, e.g. see Birkhoff, Lattice Theory.

Though it is no longer needed after the above, it is instructive to note that Arturo's proof of lhs|rhs follows nicely from a useful lemma. First, recall the universal properties of lcm, gcd

$$\rm\ [a,b]\:|\:n \;\iff\; a,b\:|\:n\quad where\quad\: [a,b] := lcm(a,b)$$

$$\rm n\:|\:(c,d) \;\iff\; n\:|\:c,d\quad where\quad (c,d) := gcd(c,d)$$

Employing these we immediately deduce the following "lcm divides gcd" lemma

$$\rm [a,b]\ |\ (c,d)\iff a,b\ |\ (c,d)\iff a,b\ |\ c,d$$

Now, applying this to the particular values in Arturo's lemma we deduce

$$\rm [(n,k),(m,k)]\ |\ (k,[n,m])\iff (n,k),(m,k)\ |\ k,[n,m]$$

which is true: $\rm\:(n,k),(m,k)\ |\ k\:$ and $\rm\:(n,k)\ |\ n\ |\ [n,m],\:$ and $\rm\: (m,k)\ |\ m\ |\ [n,m]\quad$ QED

$\newcommand{\lcm}{\operatorname{lcm}}$

Lemma. Let $G=\langle g\rangle$ a cyclic group. If $H$ is a subgroup of $G$, then $H$ is cyclic. Moreover if $H\neq \{e\}$ then $$H=\left\langle g^{\min\{j\in\mathbb{N}:g^j\in H\}}\right\rangle.$$

Proof. If $H=\{e\}$ ($e$ for the identity element) then $H$ is cyclic. Suppose that $H\neq \{e\}$. Then $H\subseteq \{g^n:n\in\mathbb{Z}\}$, i.e. there exist $n\in\mathbb{Z}^*$ so that $g^n\in H$. Note that $n\in\mathbb N$ or $-n\in\mathbb N$, in any case $\{j\in\mathbb{N}:g^j\in H\}\neq\emptyset$, so $$k=\min \{j\in\mathbb{N}:g^j\in H\}$$ is well defined. Now clearly, $\langle g^k\rangle\subseteq H$. In the other hand, if $g^n\in H$ for some $n\in\mathbb{Z}$ since $k\neq 0$ there exist $q,r\in \mathbb{Z}$ so that $$n=qk+r,\qquad 0\leq r\lt k.$$ If $1\leq r\lt k$ then \begin{align*} g^n &= g^{qk}g^r\\ g^ng^{-qk}&= g^r, \end{align*} since $g^{qk}=(g^k)^q\in H$, this says that $g^r\in H$ which contradicts the choose of $k$. Therefore $$g^n=g^{qk}=(g^k)^q\in\langle g^k\rangle$$ as we wanted. Therefore if $H\neq \{e\}$, $H=\langle g^k\rangle.$

In your case, you have $$a^{\lcm(m, n)} \in \langle a^m\rangle\cap\langle a^n\rangle.$$ Now, note that $a^j\in \langle a^m\rangle\cap\langle a^n\rangle$ iff $a^j\in \langle a^m\rangle$ and $a^j\in \langle a^n\rangle$ iff $m|j$ and $n|j$. Thus $$\{j\in\mathbb{N}:a^j\in \langle a^m\rangle\cap\langle a^n\rangle\}=\{j\in\mathbb{N}:m|j\text{ and } n|j\},$$ and therefore $$\min\{j\in\mathbb{N}:a^j\in \langle a^m\rangle\cap\langle a^n\rangle\}=\lcm(m,n)$$ by the definition of $\lcm$. Therefore $$\langle a^m\rangle\cap\langle a^n\rangle=\langle a^{\lcm(m,n)}\rangle.$$