The Art Gallery Guardian

lcm\lcm of more than two numbers as a formula of gcd\gcds


It is a common elementary number theory exercise to prove that lcm(a,b)=abgcd(a,b)\lcm(a,b) = \frac{ab}{\gcd(a,b)}.

A student might ask what is the lcm\lcm of three numbers. Some might think that lcm(a,b,c)=abcgcd(a,b,c)\displaystyle \lcm(a,b,c) = \frac{abc}{\gcd(a,b,c)} It isn't.

Still, one might want a formula for the lcm\lcm of three numbers. Of course one can say lcm(a,lcm(b,c))\lcm(a,\lcm(b,c)). In fact this is the common algorithm for computation. Are they ways to relate lcm\lcm and gcd\gcd without nesting those functions together?

Yes, but the formula is not so pretty. lcm(a,b,c)=abcgcd(a,b,c)gcd(a,b)gcd(b,c)gcd(a,c)\displaystyle \lcm(a,b,c) = \frac{abc \gcd(a,b,c)}{\gcd(a,b)\gcd(b,c)\gcd(a,c)}

This article shows how we can prove this result, and easily infer a more general theorem. First, we see there is a group isomorphism from the naturals to it's prime factors f:NNf:\mathbb{N} \to \mathbb{N}^\infty, f(p1e1pnen)=(e1,,en,0,0,)f(p_1^{e_1} \ldots p_n^{e^n}) = (e_1,\ldots,e_n,0,0,\ldots), where pnp_n is the nnth prime.

It's easy to show lcm(a1,a2,,an)=f1(max(f(a1),,f(an)))gcd(a1,a2,,an)=f1(min(f(a1),,f(an)))\displaystyle \begin{aligned} \lcm(a_1,a_2,\ldots,a_n) &= f^{-1} (\max(f(a_1),\ldots,f(a_n)))\\ \gcd(a_1,a_2,\ldots,a_n) &= f^{-1} (\min(f(a_1),\ldots,f(a_n))) \end{aligned} where max\max and min\min are defined coordinate-wise. In fact we only need to concern with one single coordinate. So the problem become proving max(a,b,c)=a+b+c+min(a,b,c)(min(a,b)+min(b,c)+min(a,c))\displaystyle \max(a,b,c) = a+b+c+\min(a,b,c)-(\min(a,b)+\min(b,c)+\min(a,c)) , then the formula for lcm\lcm of 3 numbers holds.

This look familiar to the inclusion-exclusion principle, and certainly we can use it to prove it and generalize! Let μ\mu be the Lebesgue measure, then for a finite sequence of non-negative reals {ai}\set{a_i}, max(a1,,an)=μ(i=1n[0,ai]).\displaystyle \max(a_1,\ldots,a_n) = \mu(\bigcup_{i=1}^n [0,a_i]). It's just some standard arguments to show max\max does have the inclusion-exclusion structure. It generalize to allow negative reals by simply add a large enough constant to make them positive, and subtract the constant from the result. Formulas for min,gcd,lcm\min,\gcd,\lcm follows similarly.

Posted by Chao Xu on .
Tags: number theory.