LCM ! Not so easy .

If a , b N a,b \in N such that LCM of a a n d b a \ and \ b is 700 700 , then how many such ordered pairs (a,b) are possible ?

LCM denotes Least Common Multiple.

N is the set of Natural numbers.


The answer is 75.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Pratik Shastri
Dec 1, 2014

First, prime-factorize 700 700 . 700 = 5 2 2 2 7 1 700=5^2 \cdot 2^2 \cdot 7^1

Now, let a = 5 a 1 2 a 2 7 a 3 a=5^{a_1} \cdot 2^{a_2} \cdot 7^{a_3} and b = 5 b 1 2 b 2 7 b 3 b=5^{b_1} \cdot 2^{b_2} \cdot 7^{b_3} .

Note that for LCM ( a , b ) = 700 \text{LCM}(a,b)=700 , max { a i , b i } \max\{a_i,b_i\} has to be equal to the power of the corresponding prime factor in the prime factorization of 700 700 . Let us call that power p i p_i .

So, max { a i , b i } = p i \max\{a_i,b_i\}=p_i and p 1 = 2 , p 2 = 2 , p 3 = 1 p_1=2, \ p_2=2, \ p_3=1 .

Now as we need ordered pairs ( a , b ) (a,b) , we can have the following three cases for i = 1 , 2 , 3 i=1,2,3 -

  • a i > b i , max { a i , b i } = a i a_i>b_i, \ \max\{a_i,b_i\}=a_i

  • b i > a i , max { a i , b i } = b i b_i>a_i, \ \max\{a_i,b_i\}=b_i

  • a i = b i a_i=b_i

The first two can be achieved in p i p_i ways each, and the last can be achieved in only one way. Hence, the total number of ways of having max { a i , b i } = p i \max\{a_i,b_i\}=p_i is 2 p i + 1 2p_i+1 .

Therefore, by rule of product, the number of ordered pairs is i = 1 3 ( 2 p i + 1 ) = 75 \prod_{i=1}^{3} (2p_i+1)=\boxed{75}

Very good . Hats off .

Utsav Singhal - 6 years, 6 months ago

Fantastic solution.

indulal gopal - 6 years, 6 months ago

Ditto, But your generalization as 2p+1 is good.

Chandrachur Banerjee - 6 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...