Sunday, February 19, 2012

2012/023) if GCD(a,b) and LCM(a,b) are given, how can we find a,b?

Let m = GCD(a,b)
n = LCM(a,b)

find k = n/m

now prime factorize k = p1^q1p2^q2... pr^q2

from that factorize k into product of 2 co-primes x and y.( or 1, k) with x < y

then numbers are mx and my

to illustrate

let GCD = 12 LCM = 144

k = 144/12 = 12 = 2^2*3

so the factors x, y are (1, 12),( 2^2,3)

so numbers are (12,144), (48,36)

No comments: