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

Solution 1:

$\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.

Solution 2:

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]$$

Solution 3:

$\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 election 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.$$