# n-ary version of gcd$(a,b)\space$lcm$(a,b)$ = $ab$

This question was motivated by pondering this lcm identity.

Consider that $\gcd(1,6,15) = 1$, but $\operatorname{lcm}(1,6,15)=30$, but $1\cdot 6\cdot 15 = 90$. $(2,6,15)$ shows a similar phenomenon.

So what is the correct identity for $n$-ary $\gcd$/$\operatorname{lcm}$?

-

For $n \ge 2$ there isn't just one identity; there are actually $n+1$ identities, half of which are dual to the other half, and two of which are the trivial identity $a_1 ... a_n = a_1 ... a_n$. The first two are as follows. Let $P = a_1 ... a_n$. Then

$\displaystyle a_1 ... a_n = \text{gcd}(a_1, a_2, ... a_n) \text{lcm} \left( \frac{P}{a_1}, \frac{P}{a_2}, ... \right).$

$\displaystyle a_1 ... a_n = \text{gcd}(a_1 a_2, a_1 a_3, ..., a_{n-1} a_n) \text{lcm} \left( \frac{P}{a_1 a_2}, \frac{P}{a_1 a_3}, ..., \frac{P}{a_{n-1} a_n} \right).$

The other identities are similar. This is because "pointwise" (e.g. at a particular prime $p$) the two-variable identity is just the identity $\text{min}(a, b) + \text{max}(a, b) = a + b$ for non-negative integers $a, b$, and the above identities are the natural generalization of this one.

-
Right, so there is an inclusion-exclusion argument lurking in the background. And I believe the above can be stated as a single identity (just multiply them all together!) whilst retaining its 'character'. – Jacques Carette Aug 5 '10 at 1:35
I don't see any inclusion-exclusion argument in the background. Isn't this just splitting $x_1 + \dots + x_n$ as (smallest sum of k terms) + (largest sum of n-k terms)? – ShreevatsaR Aug 5 '10 at 16:07

Such generalizations occur frequently as problems. Below are a couple of examples - which include references to prior literature, e.g. to an inclusion-exclusion max/min proof in Polya & Szego's problem book. They're problem E2229 from the Monthly 77 1970 p. 402; problem 1344 from Math. Mag. 64 1990 p. 134.

-