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.

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$!

- long long lcm(long long a, long long b) {
- return a == 0 ? 0 : a / gcd(a, b) * b;
- }

Notice two things:

- We divide $\operatorname{gcd}(a,b)$ first before multiplying by $b$. This is to avoid
**overflow**; $ab$ may exceed the bounds of`long long`

. - If $a = 0$, we immediately return $0$. This is to avoid dividing by $0$.

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?

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!

*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.