# Self dual GCD/LCM identity in Landau's Elementary Number Theory

In Landau's Elementary Number Theory (Chelsea N.Y.) in Section 1, Chapter III, Problem 3 is the following self-dual identity:

$$\gcd(\mbox{lcm}(a,b), \mbox{lcm}(b,c), \mbox{lcm}(a,c)) = \mbox{lcm}(\gcd(a,b), \gcd(b,c), \gcd(a,c)).$$

Landau evidently intends for the reader to prove it using unique factorisation, which is straightforward.

I can also see how to prove it from first principles (using only the well-known identities $\gcd(a,b)\mbox{lcm}(a,b) = ab$ and $\gcd(\mbox{lcm}(a,b),\mbox{lcm}(a,c)) = \mbox{lcm}(a,\gcd(b,c))$ and its dual):

Note $\gcd(a,b)$ divides $\mbox{lcm}(a, b)$, $\mbox{lcm}(b,c)$ and $\mbox{lcm}(a, c)$. Thus it divides their gcd, which is the left side of the identity. Similarly for $\gcd(b,c)$ and $\gcd(a,c)$. As all three values divide the left side so must their lcm. Thus the right side of the identity divides the left.

Any divisor of the left side must divide $\mbox{lcm}(a, b)$, $\mbox{lcm}(b, c)$ and $\mbox{lcm}(a, c)$, i.e. it must divide $ab/\gcd(a, b)$, $ab/\gcd(b, c)$ and $ac/\gcd(a, c)$. Thus it must divide $\gcd(ab/\gcd(a, b), bc/\gcd(b, c), ac/\gcd(a, c))$. It then certainly divides $\gcd(ab/\gcd(a, b, c), bc/\gcd(a, b, c), ac/\gcd(a, b, c)) = \gcd(ab, bc, ac)/\gcd(a, b, c)$. I claim this is precisely the right side of the identity.

To show this, let us rewrite the right side of the identity. It is in turn $$\mbox{lcm}(\gcd(a,b), \mbox{lcm}(\gcd(b,c), \gcd(a,c))) = \frac{\gcd(a,b)\mbox{lcm}(\gcd(b,c), \gcd(a,c))}{\gcd(\gcd(a,b), \mbox{lcm}(\gcd(b,c), \gcd(a,c)))}$$

$$= \frac{\gcd(a,b)\mbox{lcm}(\gcd(b,c), \gcd(a,c))}{\gcd(a,b,c, \mbox{lcm}(a,b))} = \frac{\gcd(a,b)\mbox{lcm}(\gcd(b,c), \gcd(a,c))}{\gcd(a,b,c)}$$

$$= \frac{\gcd(a,b)\gcd(c,\mbox{lcm}(a,b))}{\gcd(a,b,c)} = \frac{\gcd(c \gcd(a,b), ab)}{\gcd(a,b,c)} = \frac{\gcd(ac, bc, ac)}{\gcd(a,b,c)},$$

as claimed.

As the left side divides the right and conversely, the two sides are equal.

My question is, can this identity be proved without unique factorisation, but using other (preferably simpler) well-known identities for the LCM and GCD, i.e. without arguing from first principles?

• First glance suggests this requires a PID. – Eric Towers Feb 11 '14 at 0:30
• @Eric, I think it holds in every GCD domain modulo units. – lhf Feb 11 '14 at 0:45
• Presumably a $k$-ary version holds generically for distributive lattices. – blue Feb 11 '14 at 2:10
• @seaturtles Actually, the obvious k-ary generalisation seems to be false. – Bill Feb 11 '14 at 14:44

I think I may have the answer.

Surely by a dual argument to the series of equalities above, the left side of the identity is $$\frac{\mbox{lcm}(ab, bc, ac)}{\mbox{lcm}(a, b, c)}.$$

Thus it only remains to show

$$\mbox{lcm}(ab, bc, ac)\gcd(a, b, c) = abc$$

and

$$\gcd(ab, bc, ac)\mbox{lcm}(a, b, c) = abc$$

which are identities due to Gelin (see Dixon's History of Number Theory, vol. 1, pp. 335), and in any case, easy to prove.

I will therefore settle for a simpler argument than the one I have given, which still doesn't use unique factorisation, if one exists.