```
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 Dushyant (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.