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.