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?

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


$$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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