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$ Sep 22 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$
    – Asinomas
    Sep 22 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$ Sep 22 at 16:08
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$ Sep 22 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$
    – Asinomas
    Sep 22 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$
    – Asinomas
    Sep 22 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$ Sep 22 at 19:34
  • 1
    $\begingroup$ The case $G,L$ is the same as the case $1,L/G$ $\endgroup$
    – Asinomas
    Sep 23 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$

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.