3
$\begingroup$

Given $x$ & $y$. Count the number of distinct sequences $a_1, a_2, \dots, a_n$ $(\forall  a_i \ge 1)$ consisting of positive integers such that $\gcd(a_1, a_2, \dots, a_n) = x$ and $\sum_{i=1}^n a_i =y$.

$\endgroup$
3
$\begingroup$

First, it is obvious that if $x\not | \ \ y$, then such sequence does not exist. Therefore we suppose $x | y$.

We first enumerate the number of positive sequences $a_1, \cdots, a_n$ such that $x|a_i$ for all $i$ and $\sum_{i=1}^n a_i = y$. By taking $a_i' = \frac{a_i}{x}$ for each $i$ this means a positive sequence $a_1', \cdots, a_n'$ such that $\sum_{i=1}^n a_i' = \frac yx$. It is a combinatoric fact that there are $p(x, y, n) := \binom{\frac yx - 1}{n-1}$ of them.

Note that among the sequences considered above, there are sequences with higher gcd. We denote by $g(x, y, n)$ the number of positive sequences $a_1, \cdots, a_n$ satisfying $\gcd(a_1, \cdots, a_n) = x$ and $\sum_{i=1}^n a_i = y$, then we know that

$$ \sum_{\substack{{u > 0}\\{u | \frac yx}}} g(ux, y, n) = p(x, y, n) $$

By Möbius inversion formula, we see that

$$ g(x, y, n) = \sum_{\substack{{u > 0}\\{u | \frac yx}}} \mu(u) p\left(ux, y, n\right) = \sum_{\substack{{u > 0}\\{u | \frac yx}}} \mu(u) \binom{\frac{y}{ux}-1}{n-1}, $$

where

$$ \mu(u) = \begin{cases} 0, &\mbox{if } u \mbox{ is not square free};\\ (-1)^{\omega(u)}, &\mbox{if } u \mbox{ is a product of } \omega(u) \mbox{ distinct primes}, \end{cases} $$

is the Möbius function.

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