3
$\begingroup$

How to prove associative property of the Least common multiple (lcm). i.e,

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

My Approach:

Thanx to @Mastrem for the hint.

Using the fundamental theorem of Arithmetic, $$ a=2^{a_{2}}.3^{a_{3}}.5^{a_{5}}......=\prod_{p} p^{a_p}\quad b=2^{b_{2}}.3^{b_{3}}.5^{b_{5}}......=\prod_{p} p^{b_p}\\ lcm(a,b)=\prod_p p^{\max(a_p,b_p)} $$ Using that, $$ lcm(a,b,c)=lcm(a,lcm(b,c))=lcm(a,\prod_p p^{\max(b_p,c_p)})=\prod_p p^{\max(a_p,\prod_p p^{\max(b_p,c_p)})} $$ Similarly, $$ lcm(a,b,c)=lcm(lcm(a,b),c)=lcm(\prod_p p^{\max(a_p,b_p)},c)=\prod_p p^{\max(\prod_p p^{\max(a_p,b_p)},c_p)} $$ How do I proceed further and equate the RHS of both the equations and complete the proof ?

$\endgroup$
  • $\begingroup$ $\min(A,B,C) =\ min(A, \min(B,C))=\ min( \min(A,B),C)$ $\endgroup$ – Guy Fsone Dec 30 '17 at 16:31
  • $\begingroup$ it'd be very helpful to mention why thr s downvotes ? $\endgroup$ – ss1729 Dec 30 '17 at 17:13
  • 1
    $\begingroup$ Some people may be downvoting because you have not provided any context, for example, your attempts to solve the problem or any examples you have tried. $\endgroup$ – zz20s Dec 30 '17 at 18:19
  • $\begingroup$ @GuyFsone thnx. i hv modified the original post. could u pls assist to complete the proof, how do i apply the assoiciate property of max here ? $\endgroup$ – ss1729 Dec 31 '17 at 12:06
  • $\begingroup$ max(A,B,C)= \max(A,\max(B,C))= \max(\max(A,B),C $\endgroup$ – Guy Fsone Dec 31 '17 at 12:56
0
$\begingroup$

Hint: For every prime $p$ and natural number $n$, let $e_p(n)$ be the exponent of the highest power of $p$ dividing $n$, so $$n=\prod_{p\text{ prime}}p^{e_p(n)}$$ and use the fact that: $$\operatorname{lcm}(a,b)=\prod_{p\text{ prime}}p^{\max(e_p(a),e_p(b))}$$

$\endgroup$
  • $\begingroup$ thnx for the hint about the prime number representation of lcm. I have edited the original post. Could you pls help to proceed further. $\endgroup$ – ss1729 Dec 31 '17 at 10:57
0
$\begingroup$

If you view numbers as a sequence of prime factor exponents (which by the fundamental theorem of arithmetic is unique), then $\text{lcm}$ on two numbers is simply taking the maximum of each prime factor exponent.

Since the $\max$ function is associative, we automatically prove that $\text{lcm}$ is too. And the $\max(a, b, c)$ of three numbers is also equal to $\max(a, \max(b, c))$ by transitivity.

$\endgroup$
0
$\begingroup$

Thanx to @Guy Fsone, @Mastrem for their hints.

Using the fundamental theorem of arithmetic $$ a=p_1^{a_1}.p_2^{a_2}.p_3^{a_3}.....p_k^{a_k}=\prod_ip_i^{a_i}\\b=p_1^{b_1}.p_2^{b_2}.p_3^{b_3}.....p_k^{b_k}=\prod_ip_i^{b_i}\\c=p_1^{c_1}.p_2^{c_2}.p_3^{c_3}.....p_k^{c_k}=\prod_ip_i^{c_i} $$ where $p_{i}$ are prime numbers, i.e, $p_1=2, p_2=3, p_3=5, p_4=7, ....$so on and $$ lcm(b,c)=p_1^{max(b_1,c_1)}.p_2^{max(b_2,c_2)}.p_3^{max(b_3,c_3)}.....p_k^{max(b_k,c_k)}=\prod_ip_i^{max(b_i,c_i)}\\ lcm(a,b)=p_1^{max(a_1,b_1)}.p_2^{max(a_2,b_2)}.p_3^{max(a_3,b_3)}.....p_k^{max(a_k,b_k)}=\prod_ip_i^{max(a_i,b_i)} $$ and using the associative property of max. $$ max(a,b,c)=max(a,max(b,c))=max(max(a,b),c) $$

Now, $$ lcm(a,b,c)=lcm(a,lcm(b,c))=lcm\Big(a,p_1^{max(b_1,c_1)}.p_2^{max(b_2,c_2)}.p_3^{max(b_3,c_3)}.....p_k^{max(b_k,c_k)}\Big)=lcm\Big(p_1^{a_1}.p_2^{a_2}.p_3^{a_3}.....p_k^{a_k},p_1^{max(b_1,c_1)}.p_2^{max(b_2,c_2)}.p_3^{max(b_3,c_3)}.....p_k^{max(b_k,c_k)}\Big)=p_1^{max\big(a_1,max(b_1,c_1)\big)}.p_2^{max\big(a_2,max(b_2,c_2)\big)}.p_3^{max\big(a_3,max(b_3,c_3)\big)}.....p_k^{max\big(a_k,max(b_k,c_k)\big)}\\=p_1^{max(a_1,b_1,c_1)}.p_2^{max(a_2,b_2,c_2)}.p_3^{max(a_3,b_3,c_3)}.....p_k^{max(a_k,b_k,c_k)}=\prod_{i}p_{i}^{max(a_i,b_i,c_i)} $$ similarly, $$ lcm(lcm(a,b),c)=lcm\Big(p_1^{max(a_1,b_1)}.p_2^{max(a_2,b_2)}.p_3^{max(a_3,b_3)}.....p_k^{max(a_k,b_k)},c\Big)=lcm\Big(p_1^{max(a_1,b_1)}.p_2^{max(a_2,b_2)}.p_3^{max(a_3,b_3)}.....p_k^{max(a_k,b_k)},p_1^{c_1}.p_2^{c_2}.p_3^{c_3}.....p_k^{c_k},\Big)=p_1^{max\big(max(a_1,b_1),c_1\big)}.p_2^{max\big(max(a_2,b_2),c_2\big)}.p_3^{max\big(max(a_3,b_3).c_3\big)}.....p_k^{max\big(max(a_k,b_k),c_k\big)}\\=p_1^{max(a_1,b_1,c_1)}.p_2^{max(a_2,b_2,c_2)}.p_3^{max(a_3,b_3,c_3)}.....p_k^{max(a_k,b_k,c_k)}=\prod_{i}p_{i}^{max(a_i,b_i,c_i)} $$ Since, $lcm(a,lcm(b,c))=\prod_{i}p_{i}^{max(a_i,b_i,c_i)}=lcm(lcm(a,b),c)$, the associative property of the lcm is thus proved.

$\endgroup$

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.