nLab least common multiple




For a,ba,b \in \mathbb{N} two positive natural numbers, their least common multiple LCM(a,b)LCM(a,b) \in \mathbb{N} is the smallest natural number that is divisible by both aa and bb, i.e. such that there exist n a,n nn_a, n_n \in \mathbb{N} with n aa=n bb=LCM(a,b)n_a \cdot a = n_b \cdot b = LCM(a,b).


In the natural numbers

Spelled out, this means that the least common multiple of a,ba, b \in \mathbb{N}, denoted lcm(a,b)\mathrm{lcm}(a, b), is the element dd \in \mathbb{N} uniquely characterized by the following two conditions:

  • a|da|d and b|db|d;

  • if a|ca|c and b|cb|c, then d|cd|c.

One could equivalently equip the natural numbers with a function lcm:×\mathrm{lcm}:\mathbb{N} \times \mathbb{N} \to \mathbb{N} which satisfies the two conditions:

  • a|lcm(a,b)a|\mathrm{lcm}(a, b) and b|lcm(a,b)b|\mathrm{lcm}(a, b);

  • if a|ca|c and b|cb|c, then lcm(a,b)|c\mathrm{lcm}(a, b)|c.

It is not true that “least” means least with respect to the usual ordering \leq. In particular, 11 is the minimal element with respect to the divisibility ordering, and lcm(1,1)=1\mathrm{lcm}(1, 1) = 1 according to the definition above. However, if we construe “least” in the sense of \leq, since every natural number is a common multiple of 11 with itself, then 00 is the \leq-least natural number!

Furthermore, it is also less robust, because the notion of lcmlcm is at bottom an ideal-theoretic notion: the divisibility order on elements of a principal ideal domain is a preorder whose posetal collapse is the collection of ideals, ordered oppositely to inclusion. Thus, in ring-theoretic contexts where there is no sensible notion of \leq, for example in the ring of Gaussian integers, the notion of lcm\mathrm{lcm} still makes perfectly good sense if we use the first formulation above, expressed purely in terms of divisibility.

From the point of view of principal ideals in a pid or Bézout domain RR, the lcm corresponds to taking their meet: (lcm(a,b))=(a)(b)(\mathrm{lcm}(a, b)) = (a) \cap (b).

In an arbitrary Bézout unique factorization domain

In an arbitrary Bézout unique factorization domain RR, the least common multiple function is only a prelattice, because the minimum elements with respect to the least common multiple are given by the group of units R ×R^\times. One usually takes the quotient monoid? of the multiplicative structure on RR by the group of units R ×R^\times to get a lattice: thus, the least common multiple is a function lcm:R×RR/R ×\mathrm{lcm}:R \times R \to R/R^\times. In particular, in a discrete field KK, the quotient K/K ×K/K^\times is the boolean domain bool\mathrm{bool} and the lcm is thus a function lcm:K×Kbool\mathrm{lcm}:K \times K \to \mathrm{bool}, and in a Heyting field FF, the quotient F/F ×F/F^\times is the set of truth values Ω\Omega whose divisibility partial order is the opposite poset of the usual partial order via entailment, and the lcm is thus a function lcm:F×FΩ\mathrm{lcm}:F \times F \to \Omega, defined as lcm(a,b)isInvertible(a)isInvertible(b)\mathrm{lcm}(a, b) \coloneqq \mathrm{isInvertible}(a) \wedge \mathrm{isInvertible}(b)


Last revised on January 23, 2023 at 17:31:16. See the history of this page for a list of all contributions to it.