The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
419 views
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$.
asked in Set Theory & Algebra by Veteran (59.4k points)
recategorized by | 419 views

4 Answers

+6 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!

answered by Active (1.2k points)
selected by
+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.

answered by Boss (25.7k points)
0
dude, Its a problem of mathematical logic. Is not it?
+1
Is it asking us to write predicate logic ?? Is it mentioned in the question ??

I thought it is asking us to prove it.
0
I think.(see the topic).

But you have done good thing.
+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 )
answered by Loyal (7.6k points)
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
answered by Junior (569 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,202 questions
43,662 answers
124,114 comments
42,944 users