# About

Tag Info

Greatest common divisor and least common multiple are closely related notions in the integers and also make sense in certain other rings. The tag is intended to encompass all those questions.

The greatest common divisor of two or more integers is the largest integer that divides all of them (if it exists). It may be computed using the Euclidean algorithm.

Bézout's identity states that for non-zero integers $$a$$ and $$b$$ there exist integers $$x$$ and $$y$$ with $$ax+by=\gcd(a,b)$$.

If $$a, b \in \mathbb{N}$$, write $$a \mid b$$ if $$a$$ divides $$b$$, i.e. there is $$k \in \mathbb{N}$$ such that $$b = ka$$.

The least (or lowest) common multiple of $$a_1, \dots, a_k \in \mathbb{N}$$ is the smallest positive integer $$N$$ such that $$a_i \mid N$$ for $$i = 1, \dots, k$$. We usually denote $$N$$ by $$\operatorname{lcm}(a_1, \dots, a_k)$$. Note that $$\operatorname{lcm}(a_1, \dots, a_k)$$ can be defined recursively from a binary definition. That is,

$$\operatorname{lcm}(a_1, \dots, a_k) = \operatorname{lcm}(\operatorname{lcm}(\dots\operatorname{lcm}(\operatorname{lcm}(a_1, a_2), a_3), \dots, a_{k-1}), a_k).$$

If $$a, b \in \mathbb{N}$$ and $$a = p_1^{r_1}\dots p_m^{r_m}$$, $$b = p_1^{s_1}\dots p_m^{s_n}$$ are their prime decompositions (where some of the $$r_i$$ and $$s_j$$ can be zero), we have

$$\operatorname{lcm}(a, b) = p_1^{\max(r_1, s_1)}\dots\ p_m^{\max(r_m, s_m)}.$$

Note that $$\operatorname{lcm}(a, b)\operatorname{gcd}(a, b) = ab$$ where $$\operatorname{gcd}(a, b)$$ is the greatest common divisor of $$a$$ and $$b$$.

All of these notions can be generalised to any commutative ring; the above is just the particular case of (positive elements of) the ring $$\mathbb{Z}$$.