Combinatorics and least common multiple

79 Views Asked by At

Would you be so kind as to provide me with a hint for a question that I can't solve?

It is supposed to be more or less easy, but I don't see what the quick way to settle is. Let me thank you in advance for your help.

Question. How many $4$-tuples $(a,b,c,d) \in \mathbb{N}^{4}$ are there satisfying the following constraints $$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(b,c,d)=\mathrm{lcm}(c,d,a)= \mathrm{lcm}(d,a,b)=2^{5}3^{4}5^{3}7^{2}$$?

1

There are 1 best solutions below

2
On

I think the key observation is to solve it individually for each prime. So we first solve the following easier problem,

How many $4$-tuples exist such that $\mathrm{lcm}(a,b,c) = \mathrm{lcm}(b,c,d)=\mathrm{lcm}(c,d,a)= p^k$.

Clearly the numbers must be of the form $p^j$ with $j\leq k$. And out of these ones the ones that don't work are the following:

  • The ones that don't have a $p^k$ (there are $k^4$ of these).

  • The ones that have exactly one $p^k$ (there are $4k^3$ of these).

Therefore the number of solutions is $(k+1)^4 - k^4 - 4k^3$

We denote this number as $T_k$


The number that we are looking for is $T_5 T_4 T_3 T_2$.