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.
Best Answer
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.