### div24ever's blog

By div24ever, 4 years ago, ,
Let a = ( 2 ^ 9 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 11 ^ 1 )
and b = ( 2 ^ 2 ) * ( 3 ^ 4 ) * ( 7 ^ 1 ) * ( 13 ^ 2 )


then our answer will be ( 2 ^ 9 ) * ( 11 ^ 1 )

I can easily which factors will be present in the answer by calculating a / gcd(a,b) but i am having difficulty in finding the power of those factors. Is it possible to solve the problem using gcd and lcm? Or we will have to factorize both a and b then find the answer?

EDIT — Or is it possible to just find the factors having the exact same power? For above example it is ( 7 ^ 1 ).

For a = ( 2 ^ 3 ) * ( 3 ^ 2 ) * ( 5 ^ 3 ) * ( 7 ^ 1 )
and b = ( 2 ^ 4 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 17 ^ 2 )
it is ( 3 ^ 2 ) * ( 7 ^ 1 )


• 0

 » 4 years ago, # |   0 it's enough to factorize one number a/gcd(a, b)I doubt it may be done without factorization at all because when b = 1 use still have to factorize a
•  » » 4 years ago, # ^ |   0 But a / gcd(a,b) will give ( 2 ^ 7 ) * ( 11 ^ 1 ) which is not the required answer.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 ah, I didn't notice what expected answer is, I thought it's {2, 11}, sorry
•  » » » 4 years ago, # ^ |   0 just extract factors (in your case, 2 and 11) and get the real power from dividing the actual number a,
•  » » » » 4 years ago, # ^ |   0 That would still require to compute the powers.
 » 4 years ago, # |   0 Auto comment: topic has been updated by Dushyant (previous revision, new revision, compare).
 » 4 years ago, # |   +10 For the first problem:Compute c=a/gcd(a,b) as you said, we now have the primes we need, so now we can make their powers large enough so that gcd(c^x,a)=answer you needHow to choose x so that the answer is correct and c^x is not very large. 2 is the smallest prime so if the largest power y was on a prime p greater than 2, log2(p^y)>=y And also the maximum power is reduced by the maximum power of gcd(a,b) in c. So we choose x=log2(gcd(a,b))and calculate gcd(c^x,a)I don't know if there is another way without using the power function.