# Given the GCD and LCM of n positive integers, how many solutions are there?

Question: Suppose you know $$G:=\gcd$$ (greatest common divisor) and $$L:=\text{lcm}$$ (least common multiple) of $$n$$ positive integers; how many solution sets exist?

In the case of $$n = 2$$, one finds that for the $$k$$ distinct primes dividing $$L/G$$, there are a total of $$2^{k-1}$$ unique solutions.

I am happy to write out a proof of the $$n = 2$$ case if desirable, but my question here concerns the more general version. The $$n=3$$ case already proved thorny in my explorations, so I would be happy to see smaller cases worked out even if responders are unsure about the full generalization.

Alternatively: If there is already an existing reference to this problem and its solution, then a pointer to such information would be most welcome, too!

• @Yorch Your comment only links to the question in the case where $n=2$; for me, this case was no trouble! I am asking, specifically, about the general case: Where you have positive integers $\{a_1, \ldots, a_n\}$. Sep 22 at 15:53
• do you require that the $n$ positive integers be distinct? Are you trying to count the multisets? I think that is the only version I haven't been able to solve. Sep 22 at 16:04
• @Yorch No requirement that the integers be distinct and/but (ideally!) counting distinct solutions. If you think that you can make traction on a modified version (i.e. imposing additional constraints) then I'd still be pleased to see what you come up with. Sep 22 at 16:08

If you are interested in counting tuples $$(a_1,a_2,\dots,a_n)$$ such that $$\gcd(a_1,\dots,a_n) = G$$ and $$\operatorname{lcm}(a_1,\dots,a_n) = L$$ then we can do it as follows.

If $$L/G = \prod\limits_{i=1}^s p_i^{x_i}$$ then each $$a_i$$ must be of the form $$G \prod\limits_{j=1}^s p_i^{y_{i,j}}$$ with $$0 \leq y_{i,j} \leq x_i$$.

Hence for each prime $$p_i$$ we require that the function from $$\{1,\dots, n\}$$ to $$\mathbb N$$ that sends $$j$$ to $$y_{i,j}$$ be a function that hits $$0$$ and $$x_i$$.

The number of such functions is easy by inclusion-exclusion for $$x_i \geq 1$$, it is $$(x_i+1)^n - 2(x_i)^n + (x_i-1)^n$$.

It follows the total number of tuples is $$\prod\limits_{i=1}^s ( (x_i+1)^n - 2x_i^n + (x_i-1)^n)$$.

• Counting tuples as in, with repetition, right? E.g. $(1,2)$ and $(2,1)$ would each be counted in your computation? If so, isn't it the case that (using your notation) you could assign the $s$ distinct primes (to their various powers) as divisors of any of the $n$ integers or a subset of them (e.g. to $\{a_1, a_3, a_7\}$)? There are $2^n$ subsets of $\{a_1, \ldots, a_n\}$, but we exclude the full set (this is the $\gcd$) as well as the empty set for a total of $2^{n} - 2$ subsets. Assigning the aforementioned $s$ primes can now be done in in $s^{2^{n} - 2}$ ways. Or have I misunderstood? Sep 22 at 17:17
• Yes, that is what it looks like when no prime appears more than once in $L/G$, you would get $(2^n-2)^s$@BenjaminDickman , when you have a prime with exponent greater than $1$ dividing $L/G$ it becomes more complex. Sep 22 at 17:49
• lets consider $G=1$ and $L=8$ and $n = 3$. Here we must have that each $a_i$ is one of $1,2,4,8$, and we require that at least one of them is $1$ and at least one of them is $8$, there are $4^3$ total tuples, there are $3^3$ tuples that don't hit the value one, there are $3^3$ that don't hit the value $8$ and there are $2^3$ that don't hit etiher, so there are $4^3-2(3^3) + 2^3$ total triples that work. Sep 22 at 18:08
• Ah, great! I have also been pointed to this same answer as Theorem 2.7 here: derby.openrepository.com/handle/10545/583372 (I may add an answer to this effect) Sep 22 at 19:34
• The case $G,L$ is the same as the case $1,L/G$ Sep 23 at 16:39

(Adding this community wiki answer to point out a relevant reference.) I was recently pointed to the following paper, in which this and related problems are proposed and solved:

Bagdasar, O. (2014.) "On some functions involving the lcm and gcd of integer tuples." Scientific Publications of the State University of Novi Pazar Series A: Applied Mathematics, Informatics and mechanics, 6(2):91-100. PDF (no paywall).

The result appears as Theorem 2.7 (cf. the comment of Yorch, too): 