dush1729's blog

Given two numbers a and b. Find those factors whose power in a is strictly greater than b using property of gcd and lcm if possible?
By dush1729, 9 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

»
9 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

→ Reply
  • »
    »
    9 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.

    → Reply
    • »
      »
      »
      9 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

      → Reply
    • »
      »
      »
      9 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,

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

        That would still require to compute the powers.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 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.

→ Reply