Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$?

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
1  
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
1  
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
add comment

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.

alt text alt text alt text

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.