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

Follow

Get every new post delivered to your Inbox.

Join 202 other followers