44
$\begingroup$

How can I prove that if $G$ is an Abelian group with elements $a$ and $b$ with orders $m$ and $n$, respectively, then $G$ contains an element whose order is the least common multiple of $m$ and $n$?

It's an exercise from Hungerford's book, but it's not homework. I could not solve it when I take the course on groups and I think it should be easy. There is a hint that says to first prove when $m$ and $n$ are coprimes. I did this part. But I have no idea how to solve the general case.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Yes, this is a great exercise in Hungerfold's book. $\endgroup$ – Yilong Zhang Jun 24 '15 at 13:14
  • $\begingroup$ this was a neat problem. can anyone think of a counterexample for nonabelian groups? $\endgroup$ – David Warren Katz Jul 14 '16 at 23:45
  • $\begingroup$ The dihedral group of order 6: take the rotation $a$ of order $3$ and a reflection $b$ of order $2$, but the dihedral group has no element of order $6$. $\endgroup$ – Student Feb 19 '17 at 12:27
  • $\begingroup$ This is also exercise 10.E.1 in Pinter. $\endgroup$ – dharmatech Sep 26 '17 at 2:20
25
$\begingroup$

Below is a simple inductive proof excerpted from my post in a prior thread.

Lemma $\ $ A finite abelian group $\rm\,G\,$ has lcm-closed order set, i.e. with $\rm\, o(X) := $ order of $\rm\: X$

$$\rm X,Y \in G\ \ \Rightarrow\ \ \exists\ Z \in G\!:\ o(Z) = lcm(o(X),o(Y))\qquad\ \ \ \ \ $$

Proof $\ \ $ We induct on $\rm\, o(X)\, o(Y).\, $ If it's $\,1\,$ let $\rm\:Z = 1.\:$ Else split off $\rm\,p's$ in $\rm\,o(X),\,o(Y),\,$ i.e.

write $\rm\ \ o(X)\, =\, AP,\: \ \ o(Y) = B\bar P,\, $ prime $\rm\: p\nmid A,B,\, $ wlog $\rm\,p\,$ $\rm\color{#0a0}{highest}$ in $\,\rm P\,$ so $\,\rm\color{#0a0}{\bar P\!\mid P}\! =\! p^{\large k} > 1 $

Then $\rm\: o(X^{\large P}) = A,\ \ o(Y^{\large \bar P}) = B.\ $ By induction $\rm\, \exists\, Z\!:\ o(Z) = lcm(A,B)$

so $\rm\,\ \ o(X^{\large A}\,\!Z) =\, P\, lcm(A,B) = lcm(AP,B\bar P) = lcm(o(X),o(Y))\,\ $ by here.

Note $ $ This is an element-wise form of what's known as "Herstein's hardest problem": $2.5.11$, p. $41$ in the first edition of Herstein's popular textbook Topics in Algebra. In the 2nd edition Herstein added the following note (problem $2.5.26$, p. $48$)

Don't be discouraged if you don't get this problem with what you know of group theory up to this stage. I don't know anybody, including myself, who has done it subject to the restriction of using material developed so far in the text. But it is fun to try. I've had more correspondence about this problem than about any other point in the whole book."

$\endgroup$
  • $\begingroup$ @Bill: I believe the (in)famous problem was about subgroups, not elements; that is, if $G$ is abelian and $H$ and $K$ are finite subgroups, then $G$ has a subgroup of order $\mathrm{lcm}(|H|,|K|)$. In my Spanish translation of the first edition, this is problem 2.5.11. $\endgroup$ – Arturo Magidin Nov 16 '10 at 22:39
  • $\begingroup$ @Arturo: Indeed, but essentially the same proof works for the subgroup case. $\endgroup$ – Bill Dubuque Nov 16 '10 at 23:11
  • 1
    $\begingroup$ @dharmatech I misread your comment. We are pulling out all factors of the same prime $p$ from both (not different primes). So in your example for $\,p=3\,$ it should be $P = 3^{\large 2},\ \bar P = 3^{\large 0} = 1\ \ $ $\endgroup$ – Bill Dubuque Jul 31 at 16:24
  • 1
    $\begingroup$ @dharmatech We must split out all of the $p's$ so what remains $= A$ (or $B)$ is not divisible by $p.\,$ The name is "prime factorization" (but we only care about one prime $p$ so we collect the product of all the other prime factors into $A$ (or $B).\,$ It is indeed a common technique: reducing to prime powers then combining appropriately, e.g. it is used in CRT, multiplicative functions, etc. $\endgroup$ – Bill Dubuque Aug 1 at 0:18
  • 1
    $\begingroup$ @dharmatech This is a widely used technique for symmetric problems. Here the statement $\rm P(X,Y)\, :=\, \exists\ Z \in G\!:\ o(Z) = lcm(o(X),o(Y))\,$ is symmetric in $\rm X,Y$ i.e. $\rm\,P(X,Y)\!\iff\! P(Y,X),\,$ i.e. swapping the arguments yields an equivalent statement, so it suffices to prove either. $\endgroup$ – Bill Dubuque Aug 3 at 14:23
31
$\begingroup$

Let $n = \prod_i p_i^{n_i}$ and $m = \prod_i p_i^{m_i}$, where the $p_i$s are the same. Thus $\mathrm{lcm}(n,m) = \prod_i p_i^{\max(n_i,m_i)}$. Let $N = \{ i : n_i \geq m_i \}$ and $M = \{ i : n_i < m_i \}$. Define $n' = \prod_{i \in N} p_i^{n_i}$ and $m' = \prod_{i \in M} p_i^{m_i}$. Now $a' = a^{n/n'}$ is of order $n'$, and $b' = b^{m/m'}$ is of order $m'$. Since $n',m'$ are coprime, we know that there is an element of order $n'm' = \mathrm{lcm}(n,m)$.


You can also prove it using the structure theorem for abelian groups, but that's an overkill.

$\endgroup$
  • $\begingroup$ Thanks Yuval. That's a nice proof. But how would you do this using the structure theorem? Here the abelian group isn't necessarily finitely generated. So would you pick a finitely generated subgroup containing a and b? $\endgroup$ – Álvaro Garcia Nov 17 '10 at 13:59
  • 1
    $\begingroup$ Indeed, you can take the subgroup generated by $a,b$, which is going to contain the element you're looking for anyhow. $\endgroup$ – Yuval Filmus Nov 17 '10 at 14:55
  • 1
    $\begingroup$ Instead of "we know that there is an element of order $n'm'= \mathrm{lcm}(n,m)$" I'd say "the order of $a'b'$ is $n'm'= \mathrm{lcm}(n,m)$". $\endgroup$ – user26857 Jan 6 '15 at 10:12
  • $\begingroup$ $a'b'$ have order $m'n'$? Certainly $(a'b')^{m'n'} = e$, but I'm struggling to prove that. $\endgroup$ – AnalyticHarmony Apr 20 '18 at 17:40
  • $\begingroup$ @AnalyticHarmony Use $(a'b')^t=1$ and $(a')^t=(b')^{-t}$. Then take $m'$-th powers, then $1=(a')^{tm'}=(b')^{-tm'}$. We have $n'|tm'$, giving $n'|t$. Similarly, we have $m'|tn'$ giving $m'|t$. Therefore, $m'n'|t$. $\endgroup$ – Sungjin Kim Nov 4 '18 at 6:36
14
$\begingroup$

Both responses you have received provide correct answers. In fact, you don't need to go so far as to obtain elements of relatively prime orders; all you need to worry about are primes with the property that they divide $nm$, and the largest power of $p$ that divides $n$ is equal to the largest power of $p$ that divides $m$.

Lemma. Let $x$ and $y$ be commuting elements of a group $G$, and assume $x$ and $y$ are of finite orders $n$ and $m$, respectively. Suppose that for every prime $p$ that divides $nm$, the largest power of $p$ that divides $n$ is different from the largest power of $p$ that divides $m$. Then the order of $xy$ in $G$ is $\mathrm{lcm}(n,m)$.

Proof. Let $\ell=\mathrm{lcm}(n,m)$. It is easy to verify that $(xy)^{\ell}=1$, so we just need to show that $\ell$ is the smallest positive integer $k$ such that $(xy)^k=1$. Suppose that $(xy)^k = 1$, with $0\lt k\leq \ell$.

Since $(xy)^k = x^ky^k = 1$, then $x^k = y^{-k}$, and in particular $x^k$ has the same order as $y^k$. The order of $x^k$ is $n/\gcd(n,k)$, and the order of $y^k$ is $m/\gcd(m,k)$. Let $p$ be a prime that divides $\ell$, and let $a=\mathrm{ord}_p(n)$, $b=\mathrm{ord}_p(m)$, and $c=\mathrm{ord}_p(k)$. Assume $b\lt a$. If $c\lt a$, then $\mathrm{ord}_p(n/\gcd(n,k)) = a-c$, and $\mathrm{ord}_p(m/\gcd(m,k))=\max(0,b-c)\lt a-c$, which is impossible. Thus, $c=a$. A symmetric argument shows that if $a\lt b$, then $c=b$. That is, for all primes $p$ that divide $\ell$, we have $\mathrm{ord}_p(k) = \max(\mathrm{ord}_p(n),\mathrm{ord}_p(n)) = \mathrm{ord}_p(\ell)$. Hence $k=\ell$. QED

So now assume that $a$ is an element of order $n$ in an abelian group, and let $b$ be an element of order $m$. Let $p_1,\ldots,p_k$ be the primes that divide $nm$ and for which the $p$-order of $p_i$ in $m$ and in $n$ are equal. Then $$\mathrm{lcm}(n,m) = \mathrm{lcm}\left(n, \frac{m}{p_1\cdots p_k}\right).$$ Since $m/(p_1\cdots p_k)$ is the order of $b^{p_1\cdots p_k}$, then it follows from the lemma that $ab^{p_1\cdots p_k}$ has order $\mathrm{lcm}(n,m)$, as desired.

$\endgroup$
  • 1
    $\begingroup$ Very nice Arturo. It's good to know that we can do this assuming only that the elements commute. $\endgroup$ – Álvaro Garcia Nov 17 '10 at 13:59
  • 1
    $\begingroup$ @Álvaro Garcia: Well, that much is really a very simple observation: just work inside $\langle x,y\rangle$. Of course, the result is horribly false if $x$ and $y$ don't commute. All sorts of weird things can happen then. $\endgroup$ – Arturo Magidin Nov 17 '10 at 17:23
4
$\begingroup$

This is also one of the starred problems in Herstein's: Topics in Algebra book. Take a look into page 3 of this file:

In case you aren't able to view the solution i type it down as i am not able to download this file, but able to view it in Google Docs.

Solution: Let $a$ and $b$ be elements of order $m$ and $n$ respectively. Write $\text{lcm} (m,n)= \prod\limits_{i=1}^{t}p_{i}^{\alpha_{i}}$, where the $p_{i}$'s are distinct primes, and $\alpha_{i} > 0$ for each $i$. For any $i \in [1,2, \cdots,t ]$, $p_{i}^{\alpha_{i}}$ divides, either $m$ or $n$. If say, $p_{i}^{\alpha_{i}} \mid m$, then, $a^{m/p_{i}^{\alpha_{i}}}$ is of order $p_{i}^{\alpha_{i}}$. In this way we obtain elements $x_{1},\cdots,x_{t}$ of orders $p_{1}^{\alpha_{1}}, \cdots, p_{t}^{\alpha_{t}}$ respectively. Now consider elements in $G$ of the form $$x_{1}^{\beta_{1}}, \cdots, x_{t}^{\beta_{t}} \quad \cdots (3)$$ where $\beta_{i} \in \mathbb{N}$, and $i \in [1,2,\cdots,t]$.

Our next goal, is to show that, the single elements, $(x_{1},\cdots,x_{t})$ generates all elements of the form $(3)$. For this purpose, we prove that for all $\beta_{i} \in \mathbb{N}$, $i \in [1,2,\cdots t]$, the system $$ k = \beta_{1} \ (\text{mod} \ p_{1}^{\alpha_{1}})$$ $$ \cdot $$ $$\cdot $$ $$\cdot $$ $$k = \beta_{t} \ (\text{mod} \ p_{t}^{\alpha_{t}}$$ has a solution in $k$. This follows by setting $$ k =\sum\limits_{i=1}^{t} \beta_{i}c_{i} p_{1}^{\alpha_{1}} \cdots p_{i-1}^{\alpha_{i-1}}p_{i+1}^{\alpha_{i+1}} \cdots p_{t}^{\alpha_{t}}$$ where $c_{i}$ satisfies $$ c_{i} p_{1}^{\alpha_{1}} \cdots p_{i-1}^{\alpha_{i-1}}p_{i+1}^{\alpha_{i+1}} \cdots p_{t}^{\alpha_{t}} \equiv 1 \ (\text{mod} \ p_{i}^{\alpha_{i}})$$

It's not hard to see that the elements of the form in Eq.(3) form a subgroup $H$ of $G$. Hence for each $i$ the order $p_{i}^{\alpha_{i}}$ of the subgroup generated by $x_{i}$ divides $|H|$ by Lagrange's theorem. This gives $|H| \geq \prod\limits_{i=1}^{t} p_{i}^{\alpha_{i}}$. Clearly $|H| \leq \prod\limits_{i=1}^{t} p_{i}^{\alpha_{i}}$ also holds. Since the element, $(x_{1}, \cdots, x_{t})$ generates exactly $H$ it has order $|H|$

$\endgroup$
1
$\begingroup$

This becomes quite easy once you know the following structural

Theorem. Any Abelian torsion group is canonically isomorphic to the direct sum of its $p$-torsion subgroups for all prime numbers$~p$.

Here the $p$-torsion subgroup is the subgroup of elements of order some power of$~p$. Note that this is not the structure theorem for finitely generated Abelian groups, as here (1) the decomposition is canonical, (2) there is no finiteness requirement for the group, and (3) the theorem deals only with torsion elements.

To see why the theorem implies the requested result, $a$ and $b$ surely live in the torsion subgroups of $G$, and viewing that as the indicated direct sum, it suffices to prove the result in each $p$-torsion subgroup separately (applying it to the components of $a$ and $b$ in that summand, and combining the new $p$-torsion elements so found as components of a torsion element of$~G$). But in a $p$-torsion group the result is trivial: as $\operatorname{lcm}(p^i,p^j)\in\{p^i,p^j\}$, one can simply choose the element with the larger order as the new element.

The proof of the theorem is based on the property: for every prime $p$, each torsion element $x$ can uniquely be written as product of a $p$-torsion element $g$ and a co-$p$-torsion element $h$ (an element with order relatively prime to$~p$). This follows from the Chinese remainder theorem for cyclic groups, which gives that (1) if $x=gh$ is any such product, then necessarily $g$ and $h$ both lie in the cyclic group generated by $x$, and (2) within that cyclic group there is a unique such pair $g,h$. Then $g$ is the component of $x$ on the $p$-torsion subgroup. Combining these components for all $p$ provides an inverse to the obvious embedding of the direct sum of the $p$-torsion subgroups into the torsion subgroup of$~G$. The proof that it does is easy.


What happens in each $p$-torsion component is trivial, but quite unrelated to what happens at other primes. This explains why the result requires breaking up of the problem across different primes. As far as I can tell all the proofs given for this question do this in some way or another.

$\endgroup$
-3
$\begingroup$

Let $G$ be an abelian group. Let $a$ and $b$ belong to $G$ with order $m$ and $n$ respectively.

Three cases arise:

Case 1: If $m\mid n$ or $n\mid m$ then $\mathrm{lcm}(m,n)=m$ or $n$ in the two cases respectively. Hence our condition holds trivially.

Case 2: Suppose $m$ and $n$ are co-primes. Hence $\mathrm{lcm}(m,n) = mn$. By abelian property of $G$ $(ab)^{mn} = a^{mn}b^{mn} =ee=e$. If $o(ab)<mn$ then let $k$ be smallest value for which it holds. Now $a^k$ and $b^k$ must not be $= e$ as if even one of them equals $e$ then $a^k=e$ implies $m\mid k$ as $m$ is the order of $a$. Also then $b^k=e$ implies $n\mid k$ as $n$ is the order of $b$. Hence $k$ is a multiple of $m$ and $n$ and is less than $mn$. Contradiction. Hence not possible. Now if $a^k$ and $b^k$ are not equal to $e$ and $a^kb^k=e$ Then $a^k=(b^k)^{-1}$. Hence $b^k$ belongs to $\langle a\rangle$. Hence $o(b^k) \mid o(a)=m$, but $o(b^k)\mid o(b)=n$, hence $m$ and $n$ have a common factor. Contradiction. Hence $o(ab)=mn$

Case 3: Let $m$ and $n$ not be coprime. Let $d= \gcd(m,n)$. Hence $n/d$ is coprime with $m$, so $o(a)=m$ and $o(b^d)=n/d$. But as $m$ and $n/d$ are coprimes, by Case 2 we get $o(a(b^d))=(mn)/d=mn/\gcd(m,n)=\mathrm{lcm}(m,n)$. Hence we have an element which has order $\mathrm{lcm}(m,n)$.

Hence proved.

$\endgroup$
  • 1
    $\begingroup$ Case 3 is wrong: for $m=24$, $n=36$ we have $d=12$, and $(n/d,m)=(3,24)=3$, $(m/d,n)=(2,36)=2$. $\endgroup$ – user26857 Jan 6 '15 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.