recategorized by
1,918 views
15 votes
15 votes
<p><span style="line-height: 1.6;">Show that the product of the least common multiple and the greatest common&nbsp;</span><span style="line-height: 1.6;">divisor of two positive integers $a$ and $b$ is $a\times b$.</span></p>

<p>&nbsp; &nbsp; &nbsp; &nbsp;</p>
recategorized by

5 Answers

Best answer
23 votes
23 votes

$x \text{ and } y$ can be expressed as

  • $x = 2^{a_{1}}\cdot 3^{a_{2}}\ldots p^{a_{n}}.$
  • $y= 2^{b_{1}}\cdot 3^{b_{2}}\ldots p^{b_{n}}.$

where, $a_{i} \text{ & } b_{i} \geq 0$ for $1\leq i \leq n$, and $p$ is a prime number.

$x*y = 2^{a_{1}+b_{1}}\cdot 3^{a_{2}+b_{2}}\ldots p^{a_{n}+b_{n}}$

  • $\text{LCM} (x,y)  = 2^{\max(a_{1},b_{1})}\cdot 3^{\max(a_{2},b_{2})}\ldots p^{\max(a_{n},b_{n})}$
  • $\text{HCF} (x,y)  = 2^{\min(a_{1},b_{1})}\cdot 3^{\min(a_{2},b_{2})}\ldots p^{\min(a_{n},b_{n})}$

$\max(a_{i} ,b_{i}) + \min(a_{i},b_{i}) = a_{i} + b_{i}$

So, $\text{LCM}(x,y)\ast \text{HCF}(x,y) = 2^{a_{1}+b_{1}}\cdot 3^{a_{2}+b_{2}}\ldots p^{a_{n}+b_{n}} = x\ast y.$

Hence proved.

edited by
3 votes
3 votes

Let  a ( 120 ) = f1 * f2 * f3 * f4 * f5 ....  ( 2 * 2 * 2 * 3 * 5 ).

      b ( 18 )   = F1 * F2 * F3........       ( 2 * 3 * 3 )


LCM of a( 120 )  and b( 18 ) = product of elements of a union b.

                                         = M( {f1, f2, f3, f4, f5 } U { F1, F2, F3 } )    //M- > multiplication.

                                         = M( (f1/F1), f2, f3, (f4/F2), F3, f5 )   ----- (A)      // f1/ F1- > f1 or F1 


HCF of a( 120 )  and b( 18 ) = product of elements of a intersection b.   

                                         = M( {f1, f2, f3, f4, f5 } $\cap$ { F1, F2, F3 } )

                                         = M( (f1/F1), (f4/F2) )      -----------------------(B)

// Remember if a $\cap$ b= ∅, then HCF = 1.


From equation A and B,

Product of LCM and HCF =  M( (f1/F1), f2, f3, (f4/F2), F3, f5 ) M( (f1/F1), (f4/F2) ) 

                                      =  M( f1, f2, f3, f4, F3, f5,  F1, F2 )

                                      = Product of a and b.

2 votes
2 votes
lcm(x,y) : lcm of x and y

gcd(x,y):  gcd of x and y

∀x∀y( x >= 0 ∧ y>=0 ) $\rightarrow$ (LCM(x,y) * GCD(x,y) = x*y )
0 votes
0 votes
let a=2 and b=4

now lcm of a&b is 4

and hcf of a&b is 2

now if we product we'll get 8 which is equivalent  to a*b

Related questions

41 votes
41 votes
4 answers
2
ibia asked Nov 16, 2015
6,188 views
Consider the following first order formula:$\left ( \matrix{ \forall x \exists y : R(x,y) \\[1em] \Large \land \\[1em] \forall x \forall y : \left ( R(x,y) \impl...
19 votes
19 votes
3 answers
3
Kathleen asked Sep 12, 2014
5,681 views
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
52 votes
52 votes
2 answers
4
Kathleen asked Sep 12, 2014
6,358 views
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....