How do you find the lcm given the gcd and the number of ordered quadrupules

Question

Okay so I don't want to get the answer to my problem instantly (I want to try it out myself first) but I don't really have any ideas. I think the key to this problem is knowing how to find the smallest value for the $lcm$ given a number of ordered quadruples and the $gcd$.

If you think that my question is not clear enough, take a look at the problem: There are exactly 77,000 ordered quadruples $(a, b, c, d)$ such that $gcd(a, b, c, d)=77$ and $lcm(a, b, c, d)=n$ . What is the smallest possible value of $n$?

Once again I would really appreciate it if you don't just blurt out the answer, but instead give me hints if you know how to do the problem.

Thank you to all who are willing to help me!

Answer 1

One way to approach this is to use the prime factorizations to check on the limits of the powers of each prime factor and how these affect how many possible values there are for quadruples $(a,b,c,d)$. Let there be $m \ge 2$ prime factors used among $a$, $b$, $c$ and $d$, so you have

$$a = \prod_{i=1}^{m}p_i^{e_i} \tag{1}\label{eq1A}$$

$$b = \prod_{i=1}^{m}p_i^{f_i} \tag{2}\label{eq2A}$$

$$c = \prod_{i=1}^{m}p_i^{g_i} \tag{3}\label{eq3A}$$

$$d = \prod_{i=1}^{m}p_i^{h_i} \tag{4}\label{eq4A}$$

Also, have

$$\min(e_i,f_i,g_i,h_i) = q_i, \; \max(e_i,f_i,g_i,h_i) = r_i, \; 1 \le i \le m \tag{5}\label{eq5A}$$

Let $p_1 = 7$ and $p_2 = 11$. Since the $\gcd$ of a set of numbers is the product of the minimums of the exponents of their prime factors, $\gcd(a,b,c,d) = 77$ gives that

$$q_i = 1, \; i \in \{1,2\} \; \text{ and } \; q_i = 0, \; i \ge 3 \tag{6}\label{eq56}$$

Since the $\operatorname{lcm}$ of a set of numbers is the product of the maximums of the powers of their prime factors, $\operatorname{lcm}(a,b,c,d) = n$ gives that

$$n = \prod_{i=1}^{m}p_i^{r_i} \tag{7}\label{eq7A}$$

The total number of possible quadruples will be the product of the number of combinations available for the powers of each prime factor. To determine this, there are $3$ main cases to consider. Since you want to try this yourself first, I've put the details inside "spoilers" below.

---

Case #$1$: $r_i = q_i$

Since the power is the same for all of $a$, $b$, $c$ and $d$, there's only one combination.

---

Case #$2$: $r_i = q_i + 1$

Among the $4$ values, at least one must have $q_i$ factors of $p_i$ and at least one must have $r_i$. If there's one $q_i$ among the $4$ values, the other $3$ must be $r_i$. There are $4$ choices for this. For two $q_i$ among the $4$ values, with this giving $\binom{4}{2} = 6$ choices, the other $2$ must be $r_i$, so they don't provide any additional choices. Finally, there are $4$ choices for the case of $3$ values of $q_i$ and $1$ of $r_i$. This gives a total of $4 + 6 + 4 = 14$ choices.

Case #$3$: $r_i \gt q_i + 1$

Let $s_i = r_i - q_i - 1$, with this being the # of values exclusively between $q_i$ and $r_i$. As before, there must be at least one instance each of $q_i$ and $r_i$. There are various sub-cases to consider. If there's one $q_i$, so there's $4$ positions for it, then if there's also one $r_i$, among the $3$ remaining positions, then the remaining $2$ have $s_i \times s_i = s_i^2$ possibilities, for a total of $4 \times 3 \times s_i^2 = 12s_i^2$. If there's one $q_i$, among the $4$ positions, and $2$ of $r_i$ among the remaining $3$ (for $3$ choices), then the last one has $s_i$ choices, for a total of $4 \times 3 \times s_i = 12s_i$ choices in this sub-case. You can go through all of the other possible sub-cases to determine their values and add them up to get a total.

The prime factorization of $77\text{,}000$ limits which, and how many, of the cases #$2$ and #$3$ can apply. Also, of course, for any additional primes to be used in $n$, you will want to use the smallest ones available, e.g., $2$, $3$, etc., to get the smallest $n$. I'll leave it to you to do the rest.

---

Update: Note joriki provides below a simpler way to count the quadruples in cases #$2$ and #$3$ above:

There are $(q_i-r_i+1)^4$ quadruples of values between $q_i$ and $r_i$ inclusive. From this we need to subtract the $(q_i-r_i)^4$ quadruples that don’t use $q_i$ and the $(q_i-r_i)^4$ that don’t use $r_i$. But now we’ve subtracted the $(q_i-r_i-1)^4$ quadruples that use neither $q_i$ nor $r_i$ twice, so we need to add them back in. Thus, by inclusion–exclusion we find that the number of quadruples with values between $q_i$ and $r_i$ that use both $q_i$ and $r_i$ is $(q_i-r_i+1)^4-2(q_i-r_i)^4+(q_i-r_i-1)^4$.