Need help with Möbius function Suppose I need to find total subset of numbers of length $K$ in range $1$ to $N$ such that their $\gcd$ is $g$. How can I utilize Möbius function for that.
So approach is we can choose $K$ numbers out of $N/g$ numbers such that their gcd is multiple of $g$. But now we have to remove sets which have other multiples other than $g$.
 A: Informal solution
There are $\binom{\lfloor N/g\rfloor}k$ subsets of $\{g,2g,3g,\dots\}\cap \{1,2,\dots,N\}$ of size $k$. These all have a gcd which is a multiple of $g$. From these, we must subtract the sets whose gcd strictly more than $g$. For each prime such that $pg\le N$, we therefore must subtract $\binom{\lfloor N/(pg)\rfloor}k$. However, sets whose gcd is a multiple of $pqg$ for distinct primes $p\neq q$ have been subtracted twice, so these must be added back in, and so on.
The result is
$$
\sum_{d=1}^{\lfloor N/(gk)\rfloor}\mu(d)\binom{\lfloor N/(dg)\rfloor}k.\tag{$*$}
$$

Formal solution
Let $f(n)$ be the number of subsets of size $k$ whose gcd is equal to $n$. Let $h(n)$ be the number of subsets whose gcd is a multiple of $n$. Then
$$
h(n) = \sum_{n|k}f(k)
$$
This is not quite the setup we need to apply Mobius inversion; we want $k$ to range over the divisors of $n$, but here it ranges over multiples of $n$. To fix this, note that $f(k)$ is zero unless $k$ is a divisor of $N!$. Therefore, we can reindex the summation by $j:=N!/k$, and we get
$$
h(n)=\sum_{j\mid (N!/n)}f(N!/j)
$$
Now, substituting $N!/n$ for $n$, we get
$$
h(N!/n)=\sum_{j|n}f(N!/j)
$$
We can now apply Mobius inversion to $h(N!/n)$ and $f(N!/n)$, and we get
$$
f(N!/n)=\sum_{j|n}\mu(j)h(jN!/n)
$$
Finally, substituting $N!/n$ for $n$, we get
$$
f(n)=\sum_{j|(N!/n)}\mu(j)h(jn)
$$
This, coupled with $h(n)=\binom{\lfloor N/n\rfloor}{k}$, proves $(*)$.
