What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is $2^33^3$ where $x, y,z\in \Bbb N$?

What I tried :

At least one of $x, y$ and $z$ should have factor $2^3$ and at least one should have factor $3^3$. I then tried to figure out the possible combinations but couldn't get the correct answer.


We use Inclusion/Exclusion.

First we find the number of (positive) triples in which each entry divides $2^33^3$. At each of $x$, $y$, $z$ we have $(4)(4)$ choices, for a total of $16^3$.

We want to subtract the number of such triples in which each entry divides $2^23^3$. There are $12^3$ such triples. There are also $12^3$ such triples in which each element divides $2^33^2$.

But we have subtracted once too many times the $9^3$ triples in which each entry divides $2^23^2$.

So the total is $16^3-2\cdot 12^3+9^3$.


Consider all candidate triples of the form: $$ (2^{a_1}3^{b_1}, 2^{a_2}3^{b_2}, 2^{a_3}3^{b_3}) $$ where for each $i \in \{1, 2, 3\}$, we have $a_i, b_i \in \{0, 1, 2, 3\}$.

We define such a candidate triple to be valid if for some $j, k \in \{1, 2, 3\}$, we have $a_j = 3$ and $b_k = 3$. Otherwise, if ($a_j \in \{0, 1, 2\}$ for all $j \in \{1, 2, 3\}$) or ($b_k \in \{0, 1, 2\}$ for all $k \in \{1, 2, 3\}$), then such a candidate triple is considered invalid.

Observe that: \begin{align*} \text{# of valid triples} &= \text{# of candidate triples} - \text{# of invalid triples} \\ &= 4^6 - (3^3 \cdot 4^3 + 4^3 \cdot 3^3 - 3^6) \end{align*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.