1

I found a recursive formula to find out LCM(least common multiple) of 3 or more numbers in a website.I checked it and it works but I can not understand it fully.Can anyone tell me what is the reasoning behind the formula with better and clear explanation. The recursive formula is

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

HK Lee
  • 19,964
awlad hossain
  • 91
  • 2
  • Please include the recursive formula so we know what formula you're talking about! – konewka Oct 15 '14 at 15:32
  • 1
    I'm guessing it was $\operatorname{lcm}(a,b,c) = \operatorname{lcm}(\operatorname{lcm}(a,b),c)$? Basically, all you do is find the least common multiple of $a$ and $b$, call it $m$. Then the least common multiple of $m$ and $c$ is the least common multiple of $a$,$b$, and $c$. – Bruce Zheng Oct 15 '14 at 15:33

2 Answers2

1

Recall the Fact : $$ A|X,\ B|X \Rightarrow {\rm lcm}\ (A,B)|X $$ Let $$ T:={\rm lcm}\ (a,b,c),\ S:={\rm lcm}\ (b,c) $$

$$b|T,\ c|T \Rightarrow S|T $$

And $$a|T\Rightarrow {\rm lcm}\ (a,S) | T $$

$$ b|S,\ c|S \Rightarrow b|{\rm lcm}\ (a,S),\ c|{\rm lcm}\ (a,S) $$

And $$a|{\rm lcm}\ (a,S) \Rightarrow T|{\rm lcm}\ (a,S) $$

HK Lee
  • 19,964
0

It’s often useful to view $\operatorname{lcm}$ and $\gcd$ as $\max$ and $\min$, respectively, applied to the exponents of each prime in the prime factorizations. It’s clear that $\max$ and $\min$ are associative in the sense that

$$ \min(x,y,z)=\min(\min(x,y),z)=\min(x,\min(y,z))\;, $$

and likewise for $\max$, and this transfers directly to $\operatorname{lcm}$ and $\gcd$.

joriki
  • 238,052