How many unordered pairs of positive integers $(a,b)$ are there such that $\operatorname{lcm}(a,b) = 126000$?

Question

How many unordered pairs of positive integers $(a,b)$ are there such that $\operatorname{lcm}(a,b) = 126000$?

Attempt:

Let $h= \gcd(A,B)$ so $A=hr$ and $B=hp$, and $$phr=\operatorname{lcm}(A,B)=3^2\cdot 7\cdot 5^3 \cdot 2^4\,.$$ Let $p = 3^a5^b7^c2^d$ and $r = 3^e 5^f 7^g 2^s$. Notice, that given $p$ and $r$, $h$ is determined, so we can count $p$ and $r$. Multiplying $p$ and $r$ we get $$pr = 3^{(a+e)} 5^{(b+f)} 7^{(c+g)} 2^{(d+s)}\,,$$ and so $a+e = 0,1,2$.

For the first case we have $0+1 = 1$ possibility, similarly $2$ and $3$ for the other cases, so the total number is $6$. For $b+f$ we have $b + f = 0,1,2,3$ giving $10$ options. Similarly for $c + g$ we have $3$ choices and for $d + h$ we have $$1+2+3+4+5 = 15$$ choices. Multiplying these together, we get $$15\cdot 3\cdot 6\cdot 10 = 60\cdot 45 = 2700\,,$$ which is not equal to the given answer of $473$.

Edit: sorry for the weird variables. I think I've fixed everything, if not, please do point it out

Answer 1

I have explained why the OP did not get a correct solution. See my comment here. Below is a generalization of the OP's problem.

For positive integers $k$ and $l$, let $f_k(l)$ denote the number of ordered $k$-tuples $(n_1,n_2,\ldots,n_k)\in\mathbb{Z}^k_{>0}$ such that $$\text{lcm}(n_1,n_2,\ldots,n_k)=l\,.$$ Observe that $f_1(l)=1$ always.

Write $$l=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\,,$$ where $p_1,p_2,\ldots,p_r$ are pairwise distinct prime natural numbers and $\alpha_1,\alpha_2,\ldots,\alpha_r\in\mathbb{Z}_{>0}$. Then, $$n_i=p_1^{\beta_{i,1}}p_2^{\beta_{i,2}}\cdots p_r^{\beta_{i,r}}$$ for some integers $\beta_{i,j}$ such that $$0\leq \beta_{i,j}\leq \alpha_j$$ for $j=1,2,\ldots,r$. However, for each $j=1,2,\ldots,r$, at least one $i\in\{1,2,\ldots,k\}$ must satisfy $\beta_{i,j}=\alpha_j$. For a fixed $j=1,2,\ldots,r$, the number of ways to make $\beta_{i,j}<\alpha_j$ for all $i=1,2,\ldots,k$ is $\alpha_j^k$. Hence, the number of ways to make $\beta_{i,j}=\alpha_j$ for some $i=1,2,\ldots,k$ is $$\big(\alpha_j+1\big)^{k}-\alpha_j^k\,.$$ This means $$f_k(l)=\prod_{j=1}^r\,\big((\alpha_j+1)^k-\alpha_j^k\big)\,.$$ In particular, $$f_2(l)=\prod_{j=1}^r\,(2\alpha_j+1)\,.$$ Now, calculate $f_2(126000)$.

Now, let $\tilde{f_k}(l)$ denote the number of unordered $k$-tuples $(n_1,n_2,\ldots,n_k)\in\mathbb{Z}^k_{>0}$ such that $$\text{lcm}(n_1,n_2,\ldots,n_k)=l\,.$$ In the case $k=2$, we have $$\tilde{f_2}(l)=\dfrac{1+f_2(l)}{2}\,.$$ Why is that so? What is $\tilde{f_2}(126000)$?

For a general value of $k$, counting unordered $k$-tuples is a tricky combinatorial problem. I think the easiest way might be using Burnside's Lemma. Using Burnside's Lemma, we have $$\tilde{f_k}(l)=\sum_{\substack{(t_1,t_2,\ldots,t_k)\in \mathbb{Z}_{\geq 0}^k\\ \sum\limits_{\mu=1}^k\,\mu\,t_\mu=k}}\,\left(\frac{f_{\sum\limits_{\mu=1}^k\,t_\mu}(l)}{\prod\limits_{\mu=1}^k\,\big(\mu^{t_\mu}\cdot t_\mu!\big)}\right)\,.$$ For example, $$\tilde{f_3}(l)=\frac{2+3\,f_2(l)+f_3(l)}{6}\,.$$

Answer 2

I can't really follow what's going on in your attempt - it doesn't help that you use some letters with multiple inconsistent meanings and seem to start off with HCF/LCM swapped.

However, writing $A=2^a3^b5^c7^d$ and $B=2^e3^f5^g7^h$ you have $\max(a,e)=4$, etc. This means there are $2\times 5-1=9$ choices for $(a,e)$: choose one to be $4$; the other is one of $5$ options, and subtract $1$ because you just counted $4,4$ twice.

So the number of ordered pairs is $9\times7\times 5\times 3$. This is $1$ less than twice the number of unordered pairs, since every pair can be ordered in two ways except for $(126000,126000)$.

Answer 3

$126000 = 2^4\cdot 3^2\cdot 5^3\cdot 7^1$

For two numbers to have an LCM of $126000$, either $a$ or $b$ has to have $2^4$ in its prime factorization, and similarly with $3^2, 5^3, $ and $7$.

We need either $a$ and/or $b$ to have $2^4$, so we assign $2^4$ to $a$ first. Then, $b$ can have a factor from $2^0$ to $2^4$, for a total of $5$ total possibilities. We do the same for if $b$ as $2^4$, so $5\cdot 2 = 10$. However, we double-counted the case where both $a$ and $b$ have $2^4$ in it, so we subtract one to get $9$.

Similarly for $3^2$, set $a$ to have $3^2$ in its factorization. There are three choices for $b$, then swap $a$ and $b$ to get $3\cdot 2$, subtract one at the end to get $5$.

Same for $5^3$, we get $7$ and for $7^1$, we get $3$. $9\cdot 5\cdot 7\cdot 3 = 945$. However, we have a special case of $(126000, 126000)$ because this can be ordered in just one way. Therefore, we add one to $945$ to get $946$, then divide by $2$ because the pairs are unordered.

Hence, the answer is $$\fbox{473}.$$

Answer 4

Think it through: to find the lowest common divisor of $a$ and $b$ you take the prime factorization of $a$ and $b$. And find the number whose prime factorization consists of the prime factors of $a$ and of $b$ and raising them to the higher power they are raised to in $a$ and $b$. In other words:

If $\{p_i\}$ are the prime factors of $a$ and/or $b$ and $a = \prod p_i^{k_i}$ ($k_i$ may be equal to $0$ if $p_i|b$ but $p_i\not \mid a$) and $b = \prod p_i^{j_i}$ (similarly $j_i$ may be $0$ if $p_i\not \mid b$ but $p_i|a$) then $\operatorname{lcm}(a,b) = \prod p_i^{\max (k_i,j_i)}$.

so if $\operatorname{lcm}(a,b)=126000 = 2^4*3^2*5^3*7$ then $a= 2^{k_1}*3^{k_2}5^{k_3}7^{k_4}$ and $b=2^{j_1}*3^{j_2}5^{j_3}7^{j_4}$ where $\max(k_i,j_i) = 4,2,3,1$

So it becomes a combinatorial matter of counting these.

This is easier if we consider ordered pairs.

One of $a$ or $b$ must have $2^4$ divide it. There is $1$ way that both $a$ and $b$ have $2^4$ divide it. There are $2$ ways that $2^4$ divides $a$ or $b$ but not the other. And the $2^0,2^1,2^2,2^3$ are four ways that $2$ may divide then others. So there are $2*4 + 1=9$ we can factor up $2^4$ between $a$ and $b$.

We can do the same for the factors $3^2,5^3, 7^1$ to get $2*2+1=5;2*3+1=7;2*1+1=3$ ways, respectively to distribute those factors.

So there are $9*5*7*3 = 945$ *ordered pairs $(a,b)$ where $\operatorname{lcm}(a,b) =126000$.

But we need unordered pairs. So we take the number of pairs where $(a,b)\ne (b,a)$ (ie; $a\ne b$) and divide by $2$. And we take the pairs where $(a,b)=(b,a)$ (ie; $a=b$) and add those.

But if $a=b$ and $\operatorname{lcm}(a,b)=\operatorname{lcm}(a,a) = 126000$ then $a=b=126000$ and there is only one such pair.

So there are $945-1 = 944$ pairs with $a\ne b$. So that is $\frac {944}2=472$ unordered pairs where $a\ne b$ and one pair where $a=b= 126000$. So there are $473$ pairs of unordered $(a,b)$ where $\operatorname{lcm}(a,b)=126000$.