Let $a$ e $b$ be two non zero natural numbers; it is known that their product equals their GCD by LCM product, that is:
$a \cdot b = LCM(a,b) \cdot GCD(n,m)$ (1)
This formula is very useful in informatics since easy algorithms exist to calculate GCD: LCM between two numbers can therefore be calculated by calculating GCD and then applying (1).
Equation (1) can be proved in many ways; proofs can be easily found on the web (here are a couple of proofs from me, for example).
A less known more general form of the (1) is the following. Let a1,…,aN be non zero natural numbers; it’s true that:
$\prod_{i=1}^{N}a_{i} = LCM(a_{1},…,a_{N})\cdot GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a^{i}, \cdot …, \cdot \frac{1}{a_{N}}\prod_{i=1}^{N}a^{i})$ (2)
which turns out to be the (1), when we put $N=2$.
Here’s a proof of (2), which is simple provided that we calculate GCD in a way which is slightly different from traditional one (obviously equivalent).
Let $a_{1},…,a_{N}$ be N non zero natural numbers; each of them can be factorized in primes number in a unique way, some of the factors could be shared among two or more than two natural numbers, some other could appear in one of the numbers factorization only (the latters are usually referred as “not shared” factors). Let now $F = f_{1},…,f_{K}$ be the set of all the prime factors appearing in all $a_{1},…,a_{N}$ factorizations. Both shared and unique factors belong to $F$. Each of the $a_{1},…,a_{N}$ factorizes as follows:
$a_{i} = \prod_{j=1}^{K}f_{j}^{e_{ij}}, i = 1, …, N$ (3)
where some of the exponents can be zero (if that specific factor does not appear in some of the $a_{i}$ factorizations). From (3), GCD and LCM can easily be defined as follows:
$LCM(a_{1}, …, a_{N}) = \prod_{j=1}^{K}f_{j}^{\max_{i=1,…,N}(e_{ij})}$ (4)
$GCD(a_{1}, …, a_{N}) = \prod_{j=1}^{K}f_{j}^{min_{i=1,…,N}(e_{ij})}$ (5)
It’s worthwhile to notice that, if any of the $f_{j}$ did not appear in all $a_{i}$ factorizations, its minimum exponent would be 0 (zero); therefore that factor would not appear in the GCD factorization, as expected (indeed using the traditional algorithm we would consider only those factors which appear in all $a_{i}$ factorizations).
Using (4) and (5) to prove (1) is trivial. Let’s focus on the proof of (2).
First, let’s calculate the GCD at right side of (2) by using (5), that is:
$GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a_{i}, …, \frac{1}{a_{N}}\prod_{i=1}^{N}a_{i})$ (6)
In other words, we’re trying to evaluate GCD of N numbers, each of them being the product of N-1 elements among $a_{i}$. The m-th of these numbers can be factorized as follows:
$\frac{1}{a_{m}}\prod_{i=1}^{N}a^{i} = \prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-e_{mj}}$ (7)
As to calculate GCD the minimum exponent must be selected, from (7) it follows that the GCD factorization j-th factor’s $f_{j}$ exponent will be $\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})$. Hence:
$GCD(\frac{1}{a_{1}}\prod_{i=1}^{N}a_{i}, …, \frac{1}{a_{N}}\prod_{i=1}^{N}a_{i})=\prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})}$ (8)
Finally, applying powers properties at the left side of (2) and putting (4) and (8) at right side of (2), we get:
$\prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}}=\prod_{j=1}^{K}f_{j}^{\max_{i=1,…,N}(e_{ij})} \cdot \prod_{j=1}^{K}f_{j}^{\sum_{i=1}^{N}e_{ij}-\max_{i=1,…,N}(e_{ij})}$ (9)
which is obviously true.
