Least common multiple

The least common multiple (LCM) of a set of integers is the least positive integer that is a multiple of all the integers in the set, unless one of the integers is zero, in which case the LCM is defined to be zero. For example, the LCM of 6 and 8 is 24, because 24 is a multiple of 6 and 8, and no smaller positive integer has this property. The LCM is also known as the lowest common multiple. Because finding the LCM is the first step of adding two reduced fractions (so they can be put under a common denominator), finding the LCM is also referred to as finding the lowest common denominator or least common denominator (LCD).

Properties

• $\operatorname{lcm}(x,y) = \operatorname{lcm}(y,x)$ (commutativity)
• $\operatorname{lcm}(0,x) = 0$
• $\operatorname{lcm}(1,x) = x$
• $\operatorname{lcm}(x,x) = |x|$
• The multiples of the LCM constitute the entire set of common multiples of a given set of integers. For example, the LCM of 6 and 8 is 24, and the entire set of common multiples of 6 and 8 is $\{..., -72, -48, -24, 0, 24, 48, 72, ...\}$; notice that all these numbers are multiples of the LCM, 24.
• The LCM is never negative, because if $-x$ is a common multiple, then so is $+x$. Also, $\operatorname{lcm}(x,y) = \operatorname{lcm}(|x|,|y|)$.
• If $S$ and $T$ are sets, then $\operatorname{lcm}(S \cup T) = \operatorname{lcm}(\operatorname{lcm}(S), \operatorname{lcm}(T))$. For example, $\operatorname{lcm}(x,y,z) = \operatorname{lcm}(x,\operatorname{lcm}(y,z)) = \operatorname{lcm}(\operatorname{lcm}(x,y),z)$ (associativity).
• $\gcd(x,y)\,\operatorname{lcm}(x,y) = |xy|$.
• $\gcd(x,\operatorname{lcm}(x,y)) = \operatorname{lcm}(x,\gcd(x,y))$. (This property is the absorption law of the lattice over the positive integers with GCD as meet and LCM as join.)
• If $x$ has prime factorization $(-1)^a p_1^{k_1} p_2^{k_2} ... p_m^{k_m}$ and $y$ has prime factorization $(-1)^b p_1^{l_1} p_2^{l_2} ... p_m^{l_m}$, then $\operatorname{lcm}(x,y) = p_1^{\max(k_1,l_1)} p_2^{\max(k_2,l_2)} ... p_n^{\max(k_n,l_n)}$. Therefore, it is possible to find the LCM of two integers by factorizing them; but much more efficient methods exist.
• $\operatorname{lcm}(cx, cy) = |c|\,\operatorname{lcm}(x,y)$ whenever $c \in \mathbb{Z}$.

Calculation

The LCM is calculated using the property above that $\gcd(x,y)\,\operatorname{lcm}(x,y) = |xy|$; efficient algorithms are known for computing the greatest common divisor. Hence:

int lcm(int x, int y)
{
     if (x == 0 || y == 0) return 0;
     else return abs(x*y)/gcd(x,y);
}

The multiplication step may cause unnecessary overflow (such as when taking the LCM of 10⁶ and 10⁹), so the following is often used instead:

int lcm(int x, int y)
{
     if (x == 0 || y == 0) return 0;
     else return abs(x/gcd(x,y)*y);
}