3
$\begingroup$

How many ordered pairs $(a,b)$ are there such that $$\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $$

I tried using a number theoretic approach, but couldn't solve it. Moreover, it was given in my combinatorics worksheet, so there must be a combinatorial approach also.

Any help will be appreciated.
Thanks.

$\endgroup$

2 Answers 2

7
$\begingroup$

Prime factorize $a=\prod p_i^{a_i}$ and $b=\prod p_i^{b_i}$, then $$\operatorname{lcm}(a,b)=\prod_i p_i^{\max(a_i,b_i)}=2^3\cdot 3^5\cdot 11^7.$$ By the fundamental theorem of arithmetic these are the same ("we can equate the exponents of the primes"), so $$2^{\max(a_1,b_1)}\cdot 3^{\max(a_2,b_2)}\cdot 11^{\max(a_3,b_3)}=2^3\cdot 3^5\cdot 11^7$$ $$\implies\max(a_1,b_1)=3\qquad\text{etc.}$$ Thus we must count the total number of choices of the six exponents to get that number of distinct $(a,b)$ (this is a fairly easy combinatorics problem). Once again we are justified by the fundamental theorem because it assures we don't have multiplicity in the answer.

$\endgroup$
5
  • $\begingroup$ So would you agree with this count: We will consider whether a has the required maximum exponent on each of the bases 2,3,11. If a has the required maximum exponent on all three bases then there are 4*6*8 choices for b. If a has the maximum exponent on only the 2 and the 3 then there are 4*6 choices for b. If a has the maximum exponent on only the 2 and the 11 then there are 4*8 choices for b. Continuing in this manner for all 8 cases I have 315 ordered pairs. $\endgroup$ May 17, 2015 at 18:59
  • 1
    $\begingroup$ @GeoffreyCritzer Sorry for the late response - actually, it's a lot easier. Consider $(a_1,b_1)$: if $a_1=3$ then there are $4$ choices for $b_1$ and there are 3 more distinct choices for $a_1$ if $b_1=3$, amounting to $7$ total. Replacing $3$ with $N$ we get $2N+1$ choices if $\max(a_i,b_i)=n$. Then $$Total = (2*3+1)(2*5+1)(2*7+1) = 1155.$$ $\endgroup$
    – theage
    May 17, 2015 at 21:21
  • 1
    $\begingroup$ Excuse my arithmetic, that's 1771, not 1155. $\endgroup$
    – theage
    May 17, 2015 at 21:30
  • $\begingroup$ Yes thank you. I agree with your argument and 7*11*15 = 1155. I see that I left out lots of choices in my 8 cases. For what its worth, the correct sum of the 8 cases is: 4*6*8 + 7*4*6 + 5*4*8 + 3*6*8 + 5*7*4 + 3*7*6 + 3*5*8 + 3*5*7 = 1155. $\endgroup$ May 17, 2015 at 23:11
  • $\begingroup$ Yes, we both did incorrect arithmetic apparently. $\endgroup$
    – theage
    May 18, 2015 at 0:19
3
$\begingroup$

Hint:

One of $a$ and $b$ has 3 prime factors 2, the other has less or equal prime factors 2.

One of $a$ and $b$ has 5 prime factors 3, the other has less or equal prime factors 3.

One of $a$ and $b$ has 7 prime factors 11, the other has less or equal prime factors 11.

There are no other prime factors in neither $a$ nor $b$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .