1. ## Number system Problem

If N= 144 How many sets of two values (a,b) are there for which the LCM (a,b) is 144 ??

What the general formula for this (with proof) ??

2. ## Re: Number system Problem

Note that $144 = 2^43^2$. Therefore one of a or b must be divisible by $2^4$, and one of a or b must be divisible by $3^2$. How many ordered pairs (a,b) satisfy these conditions?

This method definitely generalizes, but I doubt there is a general formula since it becomes one giant counting problem when N has more prime divisors.

3. ## Re: Number system Problem

Why a or b will be divisible by 2^4 or 3^2 ????

. Very confused

4. ## Re: Number system Problem

In order for LCM(a,b) to be $2^43^2$, a and b must have the form, respectively, $2^x3^u$ and $2^y3^v$ for some nonnegative integers x, y, u and v. Further, $\text{LCM}(2^x3^u,2^y3^v)=2^{\max(x,y)}3^{\max(u,v ))}$. Therefore, $\max(x,y)=4$ and $\max(u,v)=2$.

5. ## Re: Number system Problem

Yeah dude You are awesome thanks twice

6. ## Re: Number system Problem

@emakarov : We can't say intuitively that ia or b will be divisible by 2^4 or 3^2 ,right ? (can we ?)

7. ## Re: Number system Problem

Originally Posted by timkuc
We can't say intuitively that ia or b will be divisible by 2^4 or 3^2 ,right ?
We can. If the maximum power of 2 that divides either a or b is, say, 3, then there is no reason to include 2^4 as a factor of LCM(a, b). In the notation of post #4, since 2^4 is the maximum power of 2 that divides 144, we have max(x, y) = 4, so x = 4 or y = 4 or both. This means that 2^4 divides a or b or both. Similarly for 3^2.