div24ever's blog

By div24ever, 4 years ago, In English,
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 )
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But a / gcd(a,b) will give ( 2 ^ 7 ) * ( 11 ^ 1 ) which is not the required answer.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      ah, I didn't notice what expected answer is, I thought it's {2, 11}, sorry

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      just extract factors (in your case, 2 and 11) and get the real power from dividing the actual number a,

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That would still require to compute the powers.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Dushyant (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.