2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ @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\}$. $\endgroup$
    – Benjamin Dickman
    Commented Sep 22, 2021 at 15:53
  • $\begingroup$ 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. $\endgroup$
    – Asinomás
    Commented Sep 22, 2021 at 16:04
  • $\begingroup$ @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. $\endgroup$
    – Benjamin Dickman
    Commented Sep 22, 2021 at 16:08

2 Answers 2

Reset to default
6
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Benjamin Dickman
    Commented Sep 22, 2021 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asinomás
    Commented Sep 22, 2021 at 17:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asinomás
    Commented Sep 22, 2021 at 18:08
  • 1
    $\begingroup$ 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) $\endgroup$
    – Benjamin Dickman
    Commented Sep 22, 2021 at 19:34
  • 1
    $\begingroup$ The case $G,L$ is the same as the case $1,L/G$ $\endgroup$
    – Asinomás
    Commented Sep 23, 2021 at 16:39
0
$\begingroup$

(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):

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .