20
$\begingroup$

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 :(

$\endgroup$
8
  • $\begingroup$ Robert:May you show where this problem came from? $\endgroup$
    – Victor
    Commented Apr 15, 2012 at 21:09
  • 12
    $\begingroup$ @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, $\endgroup$
    – user21436
    Commented Apr 15, 2012 at 21:12
  • 3
    $\begingroup$ 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. $\endgroup$
    – anon
    Commented Apr 15, 2012 at 21:24
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Apr 15, 2012 at 21:38
  • 1
    $\begingroup$ In fancy terms, the lattice of subgroups of a cyclic group is isomorphic to the lattice of divisors of the order of the group. $\endgroup$
    – lhf
    Commented Apr 16, 2012 at 0:01

2 Answers 2

17
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ 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! $\endgroup$ Commented Apr 15, 2012 at 22:40
  • $\begingroup$ @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. $\endgroup$ Commented Apr 15, 2012 at 22:54
  • 1
    $\begingroup$ @greycatbird: The prime factorization definition tells you that the power of $p$ that divides the gcd is the smallest of the largest power dividing $m$ and the largest power dividing $n$; and the power dividing the lcm is the largest of those two. But you can also deduce it from $mn=\gcd(m,n)\mathrm{lcm}(m,n)$ by showing what is the largest power that divides $\gcd(m,n)$. $\endgroup$ Commented Aug 28, 2020 at 14:25
  • 1
    $\begingroup$ Upon trying to prove $\gcd(\text{lcm }(n,m), k)\equiv \text{ lcm }(n,m) \text{ mod }k$, as suggested, writing said gcd as a linear combination $\text{ lcm }(n,m)\cdot s +k\cdot t$, and reducing modulo $k$ leaves $s\cdot\text{lcm }(n,m)$. How is $s\cdot\text{lcm }(n,m)\equiv\text{ lcm }(n,m)\text{ mod }k$? $\endgroup$
    – user689775
    Commented Jan 5, 2023 at 23:37
  • 2
    $\begingroup$ @ArturoMagidin Coming here from upanddownintegrate's question. Note that $\operatorname{lcm}(n,m) \equiv \operatorname{lcm}(\gcd(n,k),\gcd(m,k))\pmod{k}$ is not generally true (an example from that question's comments: $n=2, m=3, k=11$ gives $6\equiv 1 \pmod{11}$). However, you never needed to show that; instead you only needed to show exactly what you showed in the lemma. $\endgroup$ Commented Jan 7, 2023 at 2:29
9
$\begingroup$

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\,[a,b] := lcm(a,b) =\: ab/(a,b)\,$ and clearing denominators, we deduce $\,\rm (k,[n,m]) = [(k,n),(k,m)]\,$ is equivalent to

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

whic is true, by both $\rm = (kkm,kkn,kmn,kmm,knn,mmn,mnn)\:$ by the distributive law. $ $ QED
For further details on the above gcd arithmetic this answer.

Dually, we 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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .