GCD-LCM problems are always fun. The solution is simple, yet it takes a long time to get there.

Here is one for you. Do not Google it because you'll obviously find the solution there.

How many unordered pairs of numbers (a,b) are there such that their GCD is 100 and their LCM is 137062800?

Noobs may try this also:
How many unordered pairs of numbers (a,b) are there such that their LCM is 137062800?

6 comments:

  1. Vinayak MehtaMarch 17, 2012 at 5:23 PM

    Bhaiya, please tell the approach.

    ReplyDelete
    Replies
    1. AnujMarch 28, 2012 at 11:35 AM

      Let us write the prime factorization of the GCD and the LCM:
      100=(2*2)*(5*5)
      137062800=(2*2*2*2)*(3*3*3)*(5*5)*(7*7*7)*37

      Now, note that for any pair (a,b), the factors (2*2)*(5*5) will be found in both of them. In other words, a and b must be multiples of GCD.

      Consider the left-over factors from the LCM (i.e. factors of LCM/GCD): (2*2)*(3*3)*(7*7*7)*37.
      The main observation is that all the 2's from these left-over factors must have come from either a or b. i.e. the 2's, 3's, 7's and 37 have a choice b/w a and b,

      So the answer is 2*2*2*2=16.
      Just to make it clear, I enumerate all the cases. Denote 2*2 by A, 3*3 by B, 7*7*7 by C and 37 by D.

      a:GCD b:GCD*A*B*C*D
      a:GCD*A b:GCD*B*C*D
      a:GCD*B b:GCD*A*C*D
      a:GCD*C b:GCD*A*B*D
      a:GCD*D b:GCD*A*B*C
      a:GCD*A*B b:GCD*A*B
      a:GCD*A*C b:GCD*B*D
      a:GCD*A*D b:GCD*B*C
      a:GCD*B*C b:GCD*A*D
      a:GCD*B*D b:GCD*A*C
      a:GCD*C*D b:GCD*A*B
      a:GCD*A*B*C b:GCD*D
      a:GCD*A*B*D b:GCD*C
      a:GCD*B*C*D b:GCD*A
      a:GCD*A*C*D b:GCD*B
      a:GCD*A*B*C*D b:GCD

      Delete
    2. Vinayak MehtaMarch 28, 2012 at 3:57 PM

      Got my mistake.

      Delete
  2. UnknownMarch 21, 2012 at 12:46 PM

    The answer to the first part is 7.
    Please Confirm

    ReplyDelete
    Replies
    1. AnujMarch 21, 2012 at 9:55 PM

      The answer is definitely a power of 2, so you need to rethink it a bit.

      Why don't people try the 2nd problem? Its a pretty tough one too.

      Delete
    2. Vinayak MehtaMarch 22, 2012 at 1:04 AM

      I'm also getting 7 for the first part.
      "The answer is definitely a power of 2"-Kahin 7^2 toh nahin.? :)

      Delete

Subscribe to: Post Comments (Atom)