## Tag Archives: least common multiple

### The least common multiple of two ideals in an algebraic integer ring

Let $K$ be an algebraic number field with ring of integers $\mathcal{O}$. Let $A$ and $B$ be ideals in $\mathcal{O}$. Suppose $A$ and $B$ factor into prime ideals as $A = \prod P_i^{k_i}$ and $B = \prod P_i^{\ell_i}$, where $k_1,\ell_i \geq 0$. Prove that $A \cap B = \prod P_i^{\max(k_i,\ell_i)}$. Prove also that $(A \cap B)(A+B) = AB$.

Note that $A \cap B$ is an ideal, and so factors as a product of prime ideals as $A \cap B = \prod P_i^{t_i}$ for some $t_i \geq 0$. Since $A \cap B \subseteq A$, we have $\prod P_i^{t_i} \subseteq \prod P_i^{k_i}$. In particular, $t_i \geq k_i$ for each $i$. Similarly, since $A \cap B \subseteq B$ we have $t_i \geq \ell_i$ for each $i$. Thus $t_i \geq \max(k_i,\ell_i)$ for each $i$. Conversely, we have $\prod P_i^{\max(k_i,\ell_i)} \subseteq A,B$, so that $\prod P_i^{\max(k_i,\ell_i)} \subseteq A \cap B$. Thus $A \cap B = \prod P_i^{\max(k_i,\ell_i)}$, as desired.

Using the previous result, we have $(A \cap B)(A + B) = \prod P_i^{\max(k_i,\ell_i)} \cdot \prod P_i^{\min(k_i,\ell_i)}$ $= \prod P_i^{\max(k_i,\ell_i) + \min(k_i,\ell_i)}$ $= \prod P_i^{k_i+\ell_i}$ $= \prod P_i^{k_i} \cdot \prod P_i^{\ell_i}$ $= AB$.

### Describe least common multiples in a UFD

Let $R$ be a unique factorization domain and let $a,b \in R$ be nonzero elements. Prove that $a$ and $b$ have a least common multiple, and describe one such multiple in terms of the factorizations of $a$ and $b$.

We begin with some remarks on the elements of a UFD. Let $R$ be a unique factorization domain, and let $S \subseteq R$ be a set of irreducibles such that (1) every irreducible in $R$ is a multiple of some element in $S$ and (2) no two elements of $S$ are multiples of each other. Then we can write every nonzero element of $R$ in the form $\prod_S s^{k_s}$, where $k_s \in \mathbb{N}$ and all but finitely many $k_s$ are zero. The fact that this product is taken over the (possibly infinite) set $S$ is okay because our exponent function $k$ comes from the “direct sum” of $\mathbb{N}$. With this in mind, we will typically not mention $S$ and simply refer to factorizations of nonzero elements in $R$ as $\prod s^{k_s}$, with the understanding that $s$ ranges over a set of representatives of irreducible classes and all but finitely many $k_s$ are zero. Using this notation, for factorizations $\prod s^{k_s}$ and $\prod s^{\ell_s}$, we have $(\prod s^{k_s})(\prod s^{\ell_s}) = \prod s^{k_s + \ell_s}$ using the usual laws of exponents (because $R$ is commutative).

Now we prove a lemma.

Lemma: Let $R$ be a UFD and let $a,b \in R$ be nonzero, where $a$ and $b$ have the factorizations $a = \prod s^{k_s}$ and $b = \prod s^{\ell_s}$. Then $a$ divides $b$ if and only if $k_s \leq \ell_s$ for all $s$. Proof: Suppose $a$ divides $b$. Then we can write $ac = b$ for some $c$, where $c = \prod s^{m_s}$. Then $\prod s^{k_s + m_s} = ac = b = \prod s^{\ell_s}$, so that $k_s + m_s = \ell_s$ for each $s$. Since these exponents are natural numbers, we have $k_s \leq \ell_s$ for all $s$. Conversely, suppose $k_s \leq \ell_s$ for all $s$; then there exists a natural number $m_s$ such that $k_s + m_s = \ell_s$. Note that all but finitely many $\ell_s$ are zero, so that all but finitely many $m_s$ are zero. Let $c = \prod s^{m_s}$. Certainly then $ac = (\prod s^{k_s})(\prod s^{m_s}) = \prod s^{k_s + m_s}$ $= \prod s^{\ell_s} = b$, so that $a$ divides $b$. $\square$

Now to the main result. Let $a,b \in R$ be nonzero elements with factorizations $a = \prod s^{k_s}$ and $b = \prod s^{\ell_s}$. Note that all but finitely many of $\max(k_s,\ell_s)$ are zero. Define $m = \prod s^{\max(k_s,\ell_s)}$. Certainly $a|c$ and $b|c$, using the lemma. Suppose now that $c = \prod s^{n_s}$ is an element of $R$ which is divisible by both $a$ and $b$. Again using the lemma, we have $k_s \leq n_s$ and $\ell_s \leq n_s$. Thus $\max(k_s,\ell_s) \leq n_s$, and thus $m$ divides $c$. Hence $m$ is a least common multiple of $a$ and $b$.

### Least common multiples exist in a PID

Let $R$ be a principal ideal domain. Prove that any two nonzero elements in $R$ have a least common multiple.

We saw in this previous exercise that the least common multiples of $a$ and $b$ are precisely the generators of the $\subseteq$-largest principal ideals contained in $(a) \cap (b)$. Since $R$ is a principal ideal domain, $(a) \cap (b) = (\ell)$ is itself principal, so that a least common multiple indeed exists.

### Definition and basic properties of least common multiples

Let $R$ be a commutative ring with 1. Given nonzero elements $a,b \in R$, a least common multiple of $a$ and $b$ is an element $\ell \in R$ such that $a|\ell$ and $b|\ell$ and if $m \in R$ such that $a|m$ and $b|m$, then $\ell|m$.

1. Prove that a least common multiple of $a$ and $b$, if it exists, is precisely a generator for the $\subseteq$-largest principal ideal contained in $(a) \cap (b)$.
2. Deduce that any two nonzero elements in a Euclidean domain have a least common multiple which is unique up to multiplication by a unit.
3. Prove that in a Euclidean domain, the least common multiple of $a$ and $b$ is $\dfrac{ab}{\mathsf{gcd}(a,b)}$.

1. Suppose first that a least common multiple $\ell$ of $a$ and $b$ exists. Then by definition, we have $a|\ell$ and $b|\ell$, so that $(\ell) \subseteq (a)$ and $(\ell) \subseteq (b)$. Thus $(\ell) \subseteq (a) \cap (b)$. Suppose now that $(m) \subseteq (a) \cap (b)$. Then $(m) \subseteq (a)$ and $(m) \subseteq (b)$, so that $a|m$ and $b|m$. Thus $\ell|m$, and we have $(m) \subseteq (\ell)$. Thus a least common multiple of $a$ and $b$, provided it exists, generates a $\subseteq$-largest principal ideal in $(a) \cap (b)$.

Suppose conversely that $(a) \cap (b)$ contains a $\subseteq$-largest principal ideal, say $(\ell)$. Then $(\ell) \subseteq (a)$ and $(\ell) subseteq (b)$, so that $a|\ell$ and $b|\ell$. Moreover, if $a|m$ and $b|m$, then we have $(m) \subseteq (a) \cap (b)$, so that $(m) \subseteq (\ell)$, and thus $\ell|m$. Thus a $\subseteq$-largest principal ideal in $(a) \cap (b)$, if it exists, is a least common multiple of $a$ and $b$.

2. Suppose $R$ is a Euclidean domain, and let $a,b \in R$ be nonzero. Now $(a) \cap (b)$ is an ideal in $R$, and thus is principal (since all ideals in a Euclidean domain are principal). Say $(a) \cap (b) = (\ell)$. Now $(\ell)$ is necessarily the $\subseteq$-largest principal ideal contained in $(a) \cap (b)$, and so (by the previous part) $\ell$ is a least common multiple of $a$ and $b$. Moreover, if $u$ is a unit in $R$, then $(u\ell) = (\ell)$. Thus the least common multiple of $a$ and $b$ is unique up to multiplication by a unit.
3. Let $d$ be a greatest common divisor of $a$ and $b$. Note that $\dfrac{ab}{d} = a \cdot \dfrac{b}{d}$, so that $(\frac{ab}{d}) \subseteq (a)$. Similarly, $(\frac{ab}{d}) \subseteq (b)$, so that $(\frac{ab}{d}) \subseteq (a) \cap (b)$. By the previous part, we have $(\frac{ab}{d}) \subseteq (\ell)$, where $\ell$ is a least common multiple of $a$ and $b$. Now note that $ax = \ell$ for some $x$; then $abx = b\ell$, so that $\frac{ab}{\ell}x = b$. In particular, $\frac{ab}{\ell}$ divides $b$. Similarly, $\frac{ab}{\ell}$ divides $a$. Thus $\frac{ab}{\ell}$ divides $d$; say $\frac{ab}{\ell} \cdot k = d$. Then $\frac{ab}{d} \cdot k = \ell$, so that $\frac{ab}{d}$ divides $\ell$, and in fact we have $(\ell) \subseteq (\frac{ab}{d})$. Thus $\frac{ab}{d}$ is a least common multiple of $a$ and $b$, as desired.

### Bounds on the index of an intersection of two subgroups

Let $G$ be a group and let $H,K \leq G$ be subgroups of finite index; say $[G:H] = m$ and $[G:K] = n$. Prove that $\mathsf{lcm}(m,n) \leq [G: H \cap K] \leq mn$. Deduce that if $m$ and $n$ are relatively prime, then $[G: H \cap K] = [G : H] \cdot [G : K]$.

Lemma 1: Let $A$ and $B$ be sets, $\varphi : A \rightarrow B$ a map, and $\Phi$ an equivalence relation on $A$. Suppose that if $a_1 \,\Phi\, a_2$ then $\varphi(a_1) = \varphi(a_2)$ for all $a_1,a_2 \in A$. Then $\psi : A/\Phi \rightarrow B$ given by $[a]_\Phi \mapsto \varphi(a)$ is a function. Moreover, if $\varphi$ is surjective, then $\psi$ is surjective, and if $\varphi(a_1) = \varphi(a_2)$ implies $a_1 \,\Phi\, a_2$ for all $a_1,a_2 \in A$, then $\psi$ is injective. Proof: $\psi$ is clearly well defined. If $\varphi$ is surjective, then for every $b \in B$ there exists $a \in A$ such that $\varphi(a) = b$. Then $\psi([a]_\Phi) = b$, so that $\psi$ is surjective. If $\psi([a_1]) = \psi([a_2])$, then $\varphi(a_1) = \varphi(a_2)$, so that $a_1 \,\Phi\, a_2$, and we have $[a_1] = [a_2]$. $\square$

First we prove the second inequality.

Lemma 2: Let $G$ be a group and let $H,K \leq G$ be subgroups. Then there exists an injective map $\psi : G/(H \cap K) \rightarrow G/H \times G/K$. Proof: Define $\varphi : G \rightarrow G/H \times G/K$ by $\varphi(g) = (gH,gK)$. Now if $g_2^{-1}g_1 \in H \cap K$, then we have $g_2^{-1}g_1 \in H$, so that $g_1H = g_2H$, and $g_2^{-1}g_1 \in K$, so that $g_1K = g_2K$. Thus $\varphi(g_1) = \varphi(g_2)$. Moreover, if $(g_1H,g_2K) = (g_1H,g_2K)$ then we have $g_2^{-1}g_1 \in H \cap K$, so that $g_1(H \cap K) = g_2(H \cap K)$. By Lemma 1, there exists an injective mapping $\psi : G/(H \cap K) \rightarrow G/H \times G/K$ given by $\psi(g(H \cap K)) = (gH,gK)$. $\square$

As a consequence, if $[G : H]$ and $[G : K]$ are finite, $[G : H \cap K] \leq [G : H] \cdot [G : K]$.

Now to the first inequality.

Lemma 3: Let $G$ be a group and $K \leq H \leq G$. Let $S$ be a set of coset representatives of $G/H$. Then the mapping $\psi : S \times H/K \rightarrow G/K$ given by $\psi(g,hK) = ghK$ is bijective. Proof: (Well defined) Suppose $h_2^{-1}h_1 \in K$. Then $h_1K = h_2K$, so that $gh_1K = gh_2K$, and we have $\psi(g,h_1K) = \psi(g,h_2K)$. (Surjective) Let $gK \in G/K$. Now $g \in \overline{g}H$ for some $\overline{g} \in S$; say $g = \overline{g}h$. Then $\psi(\overline{g},hK) = gK$, so that $\psi$ is surjective. (Injective) Suppose $\psi(g_1,h_1K) = \psi(g_2,h_2K)$. Then $g_1h_1K = g_2h_2K$; in particular, $g_1h_1 \in g_2h_2K \subseteq g_2H$, so that $g_1 \in g_2H$ and hence $g_2^{-1}g_1 \in H$. So $g_1H = g_2H$, and in fact $g_2 = g_1$. Thus $h_1K = h_2K$, and $\psi$ is injective. $\square$

As a consequence, we have $[G : H] \cdot [H : K] = [G : K]$.

Now in this case we have $H \cap K \leq H \leq G$. Thus $m$ divides $[G : H \cap K]$ and $n$ divides $[G : H \cap K]$, so that $\mathsf{lcm}(m,n)$ divides $[G : H \cap K]$. In particular, since all numbers involved are natural, $\mathsf{lcm}(m,n) \leq [G : H \cap K]$.

Finally, if $m$ and $n$ are relatively prime, then $\mathsf{lcm}(m,n) = mn$, and we have $[G : H \cap K] = mn$.

### The order of a product of commuting group elements divides the least common multiple of the orders of the elements

Let $G$ be a group with $x,y \in G$. Assume $|x| = n$ and $|y| = m$. Suppose that $x$ and $y$ commute; i.e., that $xy = yx$. Prove that $|xy|$ divides the least common multiple of $m$ and $n$. Need this be true if $x$ and $y$ do not commute? Give an example of commuting elements $x$ and $y$ such that the order of $xy$ is not equal to the least common multiple of $|x|$ and $|y|$.

Supposing that $xy = yx$, we saw in a previous theorem that $(xy)^k = x^ky^k$ for all $k$. In particular, $(xy)^{\mathsf{lcm}(|x|,|y|)} = (x^{|x|})^{|y|/\mathsf{gcd}(|x|,|y|)} (y^{|y|})^{|x|/\mathsf{gcd}(|x|,|y|)} = 1$. Thus by a previous exercise, $|xy|$ divides $\mathsf{lcm}(|x|,|y|)$.

Consider $S_3$. Note that $|(1\ 2)| = |(1\ 3)| = 2$, so that $\mathsf{lcm}(|(1\ 2)|, |(1\ 3)|) = 2$. However $(1\ 2)(1\ 3) = (1\ 3\ 2)$ has order 3, and 3 does not divide 2.

For a trivial example, consider $x \neq 1$ and let $y = x^{-1}$. Less trivially, consider $(x,y),(1,y) \in Z_2 \times Z_4$, where $Z_2 = \langle x \rangle$ and $Z_4 = \langle y \rangle$. Note that $|(x,y)(1,y)| = |(x,y^2)| = 2$, while $|(x,y)| = |(1,y)| = 4$. Thus $|(x,y)(1,y)| \neq \mathsf{lcm}(|(x,y)|,|(1,y)|)$.

### The order of an element in Sym(n) is the least common multiple of the signature of its cycle decomposition

Prove that the order of an element in $S_n$ is the least common multiple of the lengths of the cycles in its cycle decomposition.

Let $\sigma \in S_n$ have the form $\sigma = \prod_I \sigma_i$ where the $\sigma_i$ are pairwise disjoint and $\sigma_i$ is an $n_i$-cycle. Let $|\sigma| = m$, and let $\ell = \mathsf{lcm}_I\{n_i\}$. Note that since the $\sigma_i$ are disjoint, we have $\sigma_i^m = 1$; hence $n_i|m$ for each $i \in I$. By the definition of least common multiple, then, $\ell|m$. Now we also have that $\sigma^\ell = \prod_I \sigma_i^\ell = 1$, so that $m|\ell$. Since $m$ and $\ell$ are both positive, $m = \ell$. $\blacksquare$

### Compute the order of an element in a direct product of groups

Let $A$ and $B$ be groups and let $a \in A$ and $b \in B$ have finite order. Prove that the elements $(a,1)$ and $(1,b)$ commute in $A \times B$ and deduce that the order of $(a,b)$ is the least common multiple of $|a|$ and $|b|$.

First we prove a few lemmas.

Lemma 1. If $a \in G$ has finite order, say $|a| = n$, and $a^m = 1$, then $n|m$. Proof: By the division algorithm, there exist unique $(q,r)$ such that $0 \leq r < |n|$ and $m = qn + r$. Then we have $1 = a^m = a^{qn + r} = (a^n)^q a^r = a^r$. But $n$ is the least positive integer such that $a^n = 1$; hence $r = 0$ and we have $m = qn$. So $n|m$. $\square$

Lemma 2. If $a, b \in G$ such that $ab = ba$ and $\{ a^n \ |\ n \in \mathbb{Z} \} \cap \{ b^n \ |\ n \in \mathbb{Z} \} = \{ 1 \}$ (i.e., $a$ and $b$ have only trivial powers in common) then $|ab| = \mathsf{lcm}(|a|, |b|)$. Proof: Let $|a| = n_1$, $|b| = n_2$, and $|ab| = m$, and let $c = \mathsf{lcm}(n_1, n_2)$. Then using a previous theorem and Lemma 1, we have $(ab)^c = a^c b^c = 1$ so that $m|c$. Now since $(ab)^m = a^m b^m = 1$, we have $a^m = b^{-m}$. Since $a$ and $b$ have only trivial powers in common, $a^m = 1$ and $b^m = 1$, so that $n_1 | m$ and $n_2 | m$. By the definition of least common multiple, $c|m$. So $c = m$. $\square$

Lemma 3. For all $n \in \mathbb{Z}$, $(a,b)^n = (a^n, b^n)$. Proof: We have $(a,b)^0 = 1 = (1,1) = (a^0, b^0)$. We prove the lemma for $n > 0$ by induction. For the base case $n = 1$ we have $(a,b)^1 = (a,b) = (a^1, b^1)$. Now suppose the lemma holds for som $n \geq 1$; then $(a,b)^{n+1} = (a,b)^n (a,b) = (a^n,b^n) (a,b) = (a^{n+1}, b^{n+1})$. Thus by induction the lemma holds for all positive $n$. For $n < 0$, we have $(a,b)^n = ((a,b)^{-n})^{-1} = (a^{-n}, b^{-n})^{-1} = (a^n,b^n)$, and the lemma holds. $\square$

Now for the main result it suffices to show that under the hypotheses, $(a,1)$ and $(1,b)$ have only the trivial power in common. This follows because $(a,1)^n = (a^n,1)$ and $(1,b)^m = (1,b^m)$ for all $n$ and $m$, so that $(a,1)^n = (1,b)^m$ implies in particular that $a^n = 1$ and so $(a,1)^n = (1,1)$. The conclusion follows from Lemma 2. $\blacksquare$