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 )
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
But a / gcd(a,b) will give ( 2 ^ 7 ) * ( 11 ^ 1 ) which is not the required answer.
ah, I didn't notice what expected answer is, I thought it's {2, 11}, sorry
just extract factors (in your case, 2 and 11) and get the real power from dividing the actual number a,
That would still require to compute the powers.
Auto comment: topic has been updated by dush1729 (previous revision, new revision, compare).
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 need
How 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.