Count number of $m$ elements set from $\{1,2,\dots,n\}$ whose sum is multiple of $m$ I am trying to count number of $m$ elements set from $\{1,2,\dots,n\}$ whose sum is multiple of $m$.
That's number of set $\{x_1, x_2,\cdots,x_m\}$ with $x_1+x_2+\dots+x_m \equiv 0 \pmod m$.
By using a computer, I found that it seems the result is
$$\frac1m\sum_{d|m} (-1)^{m-d} \varphi(\frac md){\lfloor\frac{dn}m\rfloor\choose d }$$
but I could not prove it. Could anyone help to prove it or provide a counterexample?
 A: Phicar's suggestion in the comments is a good one. It follows from the q-binomial theorem that
$$q^\binom{m}{2} \binom{n}{m}_q = \sum_{X \subset [n] : |X| = m} q^{\sigma(X)}, \qquad (*)$$
where $\sigma(X)$ is the sum of the elements of a subset $X \subset \{1, \dots, n\}$. We are going to evaluate this expression on all complex $m$th roots of unity and sum. On the right-hand side, the only terms which survive are those with $\sigma(X) \equiv 0 \pmod m$, so we get precisely $m$ times what we want. What do we get on the left-hand side?
Say $q = e^{i2\pi k / m}$. First, $q^\binom{m}{2} = e^{i2\pi k (m-1)/2} = (-1)^{k(m-1)}$. Second, by definition
$$ \binom{n}{m}_q = \frac{(q^n - 1)(q^{n-1} - 1) \cdots (q^{n-m+1} - 1)}{(q^m-1) (q^{m-1} - 1) \cdots (q - 1)}.$$
The apparent singularities near roots of unity are all removable (this follows from (*) for example). We can evaluate $\binom{n}{m}_q$ when $q$ is a primitive $d$th root of unity, where $d \mid m$, by applying l'Hospital's rule $m/d$ times. Let $n'$ be the largest multiple of $d$ less than $n$. Then we get
$$ \frac{n'(n'-d) \dots (n'-m+d)}{m(m-d) \dots d} = \binom{n'/d}{m/d}.$$
Since there are $\varphi(d)$ primitive $d$th roots of unity, all together we get
$$\sum_{d \mid m} (-1)^{m(m-1)/d} \varphi(d) \binom{n'/d}{m/d}.$$
This is equivalent to your expression. (Regarding the sign factor, if $m$ is even then the sign factor is $(-1)^{m/d}$, so we agree in this case, while if $m$ is odd then the sign factor is always 1 and so is yours, so we agree in that case too.)
