The greatest common divisor of multiple numbers

Question

What is the cardinality of the following set

$\{{\bf x}=(x_1,\ldots,x_d): \text{each } x_i\in \{ 1,\dots,n \},\text{ and } \gcd({\bf x})=1\}$,

where $\gcd({\bf x})$ is the greatest common divisor of $x_1,\ldots,x_d$.

A condition we have is that we know the amount of prime numbers in $\{ 1,\dots,n \}$, which is denoted as $n_p$.

I think we first need to find those with $x_1<\dots<x_d$, then handle those with $x_i=x_j$, and then easily for non-monotone cases. Note that ${\bf x}$ is a row vector, so the order of $x_i$ matters.

I hope I could obtain an explicit formula for the set's cardinality by using $n,d,n_p$.

Answer 1

I do not see a simple closed formula, but here is one that uses summation.

If we ignore the requirement on the greatest common divisor, we have $d$ successive choices to make, each choice with $n$ possibilities. This would mean $n^d$ cardinality for your set.

But we must remove the elements with $\gcd>1$. For those vectors whose $\gcd$ is $2$, we can get each of them by taking a vector with choices from $\{1,2,\ldots,\left\lfloor\frac n2\right\rfloor\}$ (where $\lfloor\cdot\rfloor$ is the greatest integer function) and multiplying each vector member by $2$. So we need to remove $\left\lfloor\frac n2\right\rfloor^d$ set elements. For $\gcd=3$ we remove $\lfloor\frac n3\rfloor^d$ set elements.

For $\gcd=4$, those were included in the ones for $\gcd=2$, so we can ignore them. For $\gcd=6$, we have included them once and removed them twice, for $2$ and for $3$. So we need to add back $\left\lfloor\frac n6\right\rfloor^d$ set elements.

You probably see the idea. For $k$ prime or the product of an odd number of distinct primes, we subtract those set elements, for $k$ one or the product of an even number of distinct primes we add them, and for $k$ divisible by the square of a prime we ignore them. The Möbius mu function, $\mu(k)$, does just what we want. So your desired cardinality is

$$\sum_{k=1}^n \mu(k)\left\lfloor\frac nk\right\rfloor^d$$

There probably is a way to abbreviate that, but I don't know it. Note that I did not use or need $n_p$, though perhaps that may be usable in an abbreviation. I checked my formula with several examples in Microsoft Excel, and they all check.

Answer 2

Let $x_k = 1$ for a $k \leqslant d$. Then we have $\gcd (x_1, x_2, \cdots, x_d) = 1$ as mentioned. Having satisfied that condition, we have $d - 1$ elements to choose from the remaining $n - 1$ numbers, which are done in ${{n - 1} \choose {d - 1}}$ ways, so there are ${{n - 1} \choose {d - 1}}$ elements in your set.

Answer 3

How many sequences of length $d$ and values in $\{1, \ldots , n\}$ are there?

This is the number of variations: $n^d$.

For given prime number $p \in \mathbb{P}$. How many sequences of length $d$ and values in $\{a | a \in \{1, \ldots , n\} , p | a\}$ values are divi^dsible by $p$) are there (?

There are $\lfloor{n/p}\rfloor^d$ these sequences. We define $f(p) := \lfloor{n/p}\rfloor^d$.

Let $A_n := \{1, \ldots , n\} \cap \mathbb{P} $. $A_n = \{ p_1, \ldots, p_s \} $ where $p_s$ are primes.

For calculating result from qiestion, we apply inclusion-exclusion principle (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). From the total number of sequences: $n^d$ we must substract number of all sequences of elements divisibled by prime numbers: $f(p_1)+ \ldots + f(p_s)$. But we have got substracted sequences of elements divisibled by pairs: $(p_i, p_j), i \neq j$ twice. Hence we must add $\sum _{1\leq i<j \leq n}f(p_ip_j)$. Etc.

We get result: $n^d - \sum _{1\leq i \leq n}f(p_i) + \sum _{1\leq i<j \leq n}f(p_ip_j) - \sum _{1\leq i<j<k \leq n}f(p_ip_jp_k)+ \ldots$

finally: $$n^d - \sum_{t=1}^{n} (-1)^t \sum _{1\leq i_1<i_2<\ldots <i_t \leq n}f(p_{i_1}p_{i_2}\ldots p_{i_t}). $$