Least common multiple

Like the gcd, you probably also already know the lcm, or the lowest common multiple. If not, well, it's just the lowest positive number that is multiple of two numbers (obviously). For example, $\operatorname{lcm}(18,24) = 72$ and $\operatorname{lcm}(7,8) = 56$. By convention, we say $\operatorname{lcm}(a,0) = 0$, thus $\operatorname{lcm}(0,11) = 0$. This time though, we won't bother with negative numbers, because they just mess up our stuff.

Like the gcd, the lcm has a lot of familiar properties.

Commutativity law. $\operatorname{lcm}(a,b) = \operatorname{lcm}(b,a)$ for any $a$, $b$.

Associativity law. $\operatorname{lcm}(\operatorname{lcm}(a,b),c) = \operatorname{lcm}(a,\operatorname{lcm}(b,c)) = \operatorname{lcm}(a,b,c)$ for any $a$, $b$ and $c$.

Identity law. $\operatorname{lcm}(1,a) = \operatorname{lcm}(a,1) = a$ for any $a$.

Distributivity law. $k\operatorname{lcm}(a,b) = \operatorname{lcm}(ka,kb)$ for all $k$, $a$, $b$.

Proposition 1. $\operatorname{lcm}(a,0) = 0$ for any $a$.

Proposition 2. $\operatorname{lcm}(a,a) = a$ for any $a$.

Proposition 3. Let $a$ and $b$ have the following prime factorizations: $$a = p_1^{e_1} p_2^{e_2} p_3^{e_3} p_4^{e_4} \cdots$$ $$b = p_1^{f_1} p_2^{f_2} p_3^{f_3} p_4^{f_4} \cdots$$

where the $p_i$ are all the primes, but only finitely many of the $e_i$s or $f_i$s are nonzero. Then $$\operatorname{lcm}(a,b) = p_1^{\max(e_1,f_1)} p_2^{\max(e_2,f_2)} p_3^{\max(e_3,f_3)} p_4^{\max(e_4,f_4)} \cdots$$

This gives us a neat symmetry: gcd corresponds to min and lcm corresponds to max!

As before, Proposition 3 can be restated using $\operatorname{ord}$:

Proposition 3 (restated). For any prime $p$, $\operatorname{ord}_p(\operatorname{lcm}(a,b)) = \max(\operatorname{ord}_p(a),\operatorname{ord}_p(b))$.

Finally, there's a way to characterize coprime numbers using lcm.

Proposition 4. Two positive numbers are coprime if and only if $\operatorname{lcm}(a,b) = ab$.

Proving these things are nice exercises.

LCM and GCD

Due to the relationship of lcm and gcd with prime factorization, we can come up with some neat relationships between them. First:

Proposition 5. $\operatorname{gcd}(a,b)\cdot \operatorname{lcm}(a,b) = a\cdot b$.

Proving this is not very hard if you use Proposition 3 and the corresponding proposition for the gcd. Proposition 5 then simply follows from the fact that $\min(x,y) + \max(x,y) = x + y$, which is very easy to check.

Proposition 5 actually already gives us a way to compute the lcm quickly. By rearranging it, we get $$\operatorname{lcm}(a,b) = \frac{ab}{\operatorname{gcd}(a,b)}.$$

Thus, we can compute lcm by computing the gcd and dividing it from $ab$!

  1. long long lcm(long long a, long long b) {
  2. return a == 0 ? 0 : a / gcd(a, b) * b;
  3. }

Notice two things:

In fact, we can translate lots of identities involving min and max with identities for gcd and lcm. The following one follows from the fact that $\max(x,\min(y,z)) = \min(\max(x,y),\max(x,z))$.

Distributivity of lcm over gcd. $\operatorname{lcm}(a,\operatorname{gcd}(b,c)) = \operatorname{gcd}(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c))$.

The following one follows from the fact that $\min(x,\max(y,z)) = \max(\min(x,y),\min(x,z))$.

Distributivity of gcd over lcm. $\operatorname{gcd}(a,\operatorname{lcm}(b,c)) = \operatorname{lcm}(\operatorname{gcd}(a,b),\operatorname{gcd}(a,c))$.

The following one follows from the fact that $\min(x,\max(x,y)) = x$.

Absorption law 1. $\operatorname{gcd}(a,\operatorname{lcm}(a,b)) = a$.

The following one follows from the fact that $\max(x,\min(x,y)) = x$.

Absorption law 2. $\operatorname{lcm}(a,\operatorname{gcd}(a,b)) = a$.

See the pattern now?

The lcm-gcd identity

We can extend Proposition 5 by finding a suitable extension of the min-max identity surrounding it. For example: $$\max(x,y,z) = x + y + z - \min(x,y) - \min(x,z) - \min(y,z) + \min(x,y,z)$$ implies the following

Proposition 6. $\operatorname{lcm}(a,b,c) = \frac{abc\operatorname{gcd}(a,b,c)}{\operatorname{gcd}(a,b)\operatorname{gcd}(a,c)\operatorname{gcd}(b,c)}$.

The mirror identity $$\min(x,y,z) = x + y + z - \max(x,y) - \max(x,z) - \max(y,z) + \max(x,y,z)$$ implies the following

Proposition 7. $\operatorname{gcd}(a,b,c) = \frac{abc\operatorname{lcm}(a,b,c)}{\operatorname{lcm}(a,b)\operatorname{lcm}(a,c)\operatorname{lcm}(b,c)}$.

Once you notice the pattern, it's even possible to extend this for more than three arguments! (This actually has a relationship with the famous inclusion-exclusion principle, if you know it.) The general identity involving min and max is called the maximum-minimums identity (and minimum-maximums identity), so we can presumably call Proposition 6 and 7, and their extensions, the lcm-gcd identity and the gcd-lcm identity, respectively!

Problems

Note: If you're into more advanced maths, most of the things talked about here are just consequences of the fact that natural numbers form a bounded lattice under gcd and lcm.