Tag Info

The concepts of *greatest common divisor* (which is also known as *Highest Common Factor*) 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 questions related to these notions.

The greatest common divisor (also known as highest common factor) of two or more integers is the largest integer that divides all of them. 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$$.

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}$$.