LCM(x,y)= 2

^{max(a1+b1)}.3^{max(a2+b2)}…P^{max(an+bn)}

I think there is a mistake, shouldn't it be max(a_{i }**, **b_{i}) ?

The Gateway to Computer Science Excellence

+12 votes

Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.

+9 votes

Best answer

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

$x = 2^{a_{1}}.3^{a_{2}}\ldots P^{a_{n}}.$

$y= 2^{b_{1}}.3^{b_{2}}\ldots P^{b_{n}}.$

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

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

**LCM(x,y)**$ = 2^{max(a_{1}+b_{1})}.3^{max(a_{2}+b_{2})}\ldots P^{max(a_{n}+b_{n})}$

**HCF(x,y)**$ = 2^{min(a_{1}+b_{1})}.3^{min(a_{2}+b_{2})}\ldots P^{min(a_{n}+b_{n})}$

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

**So, LCM(x,y)*HCF(x,y)** $= 2^{a_{1}+b_{1}}.3^{a_{2}+b_{2}}\ldots P^{a_{n}+b_{n}} = x*y.$

Proved!

+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

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 )

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

∀x∀y( x >= 0 ∧ y>=0 ) $\rightarrow$ (LCM(x,y) * GCD(x,y) = x*y )

52,345 questions

60,513 answers

201,930 comments

95,354 users