Questions tagged [gcd-and-lcm]

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

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