Coprimality in Lowest Common Multiple

Suppose that we select arbitrarily a number of, say, $n$ integers, denoted by $a_1, \ldots, a_n$. If we obtain their lowest common multiple (LCM), and label it as $M := \mathrm{lcm}(a_1,\ldots,a_n)$, then take for each of the initial $n$ integers the corresponding number $k_i$ ($i = 1, \ldots, n$) such that multiplying by that number gives us the LCM, i.e. $k_i a_i = M$ for each $i$, an intriguing pattern starts to emerge: all the numbers $k_i$ are coprime, i.e. $\gcd(k_1,\ldots,k_n)=1$.

The following is an example code snippet that illustrates this phenomenon. This snippet generates a list of $n$ random integers between $0$ and $K$, obtains their LCM, extract the factor $k_i$ for each of $a_i$, where $i = 1, \ldots, n$, from the LCM and calculate the greatest common divisor (GCD) of the $k_i$'s.

Repeatedly running this code generates a different group of $n$ integers, but notice that the GCD obtained in the end is always 1.

The definitions of lcm_euclidean_general and gcd_euclidean_general in the snippet can be found in this note.

from random import randint
n, K = 4, 2000 # feel free to change the parameters here
test = [randint(0, K) for i in range(n)]
lcm = lcm_euclidean_general(*test)
smallest_k = tuple(map(lambda x: lcm // x, test))
print(gcd_euclidean_general(*smallest_k)) # 1

Why though?

To those who are familiar with the topic of coprime integers, this phenomenon should not come as a surprise. Nevertheless, a brief explanation of this fact will be presented here.

If we assume that the numbers $k_i$, where $i = 1,\ldots,n$ are not coprime, or equivalently $\gcd(k_1,\ldots,k_n) > 1$, and we call the GCD to be $G$, then we can write $k_i=Gb_i$ where $b_i$ is an integer and $G>1$. It follows that $M=Gb_ia_i$ for each $i$.

However, this also means that we can divide each of them throughout by $G$ and obtain $\frac{M}{G}=b_ia_i$ for each $i$. Note that $\frac{M}{G} < M$ because $M > 0$ and $G > 1$, and is a constant integer because $G$ is also a common factor of $M$. Note as well that since each $b_i$ is an integer, this means that $\frac{M}{G}$ is a common multiple of the $a_i$'s that is smaller than the lowest common multiple $M$? This does not make sense, right? This is where we reach a (logical) contradiction for which the only way to resolve this is to conclude that the GCD $G$ cannot be greater than 1 all along, thus the $k_i$'s from the start must be coprime!

We have thus demonstrated the technique of proof by contradiction to confirm the validity of this fact.

That's all for this post. Hopefully this fact sounds cool enough to you and prompts you to learn more about factors and multiples of integers, or even elementary number theory in general.