Problem 2561

Proof: For map $f: D \to \mathbb{Z}$, we define a map $g: D \to \mathbb{Z}$ to be
$$g(k) = \sum_{d|k} f(d), \quad \forall k \in D.$$
By Möbius transform, the map $f$ is uniquely determined by $g$:
$$f(k) = \sum_{d|k} \mu\left(\frac{k}{d}\right) g(d), \quad \forall k \in D,$$
Therefore we have
$$\begin{align} \sum_{d|m} f(d) \binom{n/d}{m/d} &= \sum_{d|m} \sum_{x|d} \mu\left(\frac{d}{x}\right) g(x) \binom{n/d}{m/d} \nonumber \\ &= \sum_{x|m} g(x) \left( \sum_{x|d, d|m} \mu\left(\frac{d}{x}\right) \binom{n/d}{m/d} \right) \tag{1} \\ &= \sum_{x|m} g(x) \left( \sum_{s|\frac{m}{x}} \mu(s) \binom{n/(xs)}{m/(xs)} \right). \nonumber \end{align}$$
We need the following Lemma: If $b|a$, then
$$\sum_{k|b} \mu(k) \binom{a/k}{b/k} \equiv 0 \pmod{a}.$$
Assuming this lemma temporarily, we prove that (A) and (B) are equivalent. (The proof of the lemma will be given later.)
“(B) ⇒ (A)” Suppose that for every $x \in D$ we have $x \mid g(x)$. The lemma implies that
$$\frac{n}{x} \mid \sum_{s|\frac{m}{x}} \mu(s) \binom{m/(xs)}{n/(xs)},$$

"(A) ⇒ (B)" Suppose that (A) holds. We use induction to prove that for $k \in D$, we always have $k|g(k)$. Suppose that we have already proved $k|g(k)$ for $k < m$ and $k \in D$. Consider case of $k = m$. By Lemma and the inductive hypothesis, we have
$$\begin{aligned} 0 &\equiv \sum_{d|m} f(d) \binom{n/d}{m/d} \equiv \sum_{x|m} g(x) \left( \sum_{s|\frac{m}{x}} \mu(s) \binom{n/(xs)}{m/(xs)} \right) \\ &\equiv g(m) \cdot \frac{n}{m} + \sum_{x|m, x<m} g(x) \left( \sum_{s|\frac{m}{x}} \mu(s) \binom{n/(xs)}{m/(xs)} \right) \\ &\equiv g(m) \cdot \frac{n}{m} \quad (\text{mod } n), \end{aligned}$$
From this we get $m|g(m)$, completing the induction.

It remains to prove the lemma. Note that
$$\sum_{k|b} \mu(k) \binom{a/k}{b/k} = \frac{a}{b} \sum_{k|b} \mu(k) \binom{\frac{a}{k}-1}{\frac{b}{k}-1},$$
Let $b = \prod_{i=1}^t p_i^{\beta_i}$ be the prime factorization. Then we only need to prove
$$\sum_{k|b} \mu(k) C_{\frac{b}{k}-1}^{\frac{b}{k}-1} \equiv 0 \pmod{p_i^{\beta_i}}.$$
for every $1 \le i \le t$. For this, we may assume that $i = 1$. Denote $p_1^{\beta_1} = p^{\beta}$. Note that
$$\begin{aligned} & \sum_{k|b} \mu(k) \binom{\frac{a}{k}-1}{\frac{b}{k}-1} \\ &= \sum_{I \subset \{1, \dots, t\}} (-1)^{|I|} \left( \frac{\prod_{i \in I} \frac{a}{p_i}}{\prod_{i \in I} \frac{b}{p_i}} - 1 \right) \\ &= \sum_{J \subset \{2, \dots, t\}} (-1)^{|J|} \left( \left( \frac{\prod_{j \in J} \frac{a}{p_j}}{\prod_{j \in J} \frac{b}{p_j}} - 1 \right) - \left( \frac{\prod_{j \in J} \frac{a}{p_j}}{\prod_{j \in J} \frac{b}{p_j}} - 1 \right) \right) \end{aligned}$$
Then it suffices to show: if $u, v$ are multiples of $p^{\beta}$, then
$$\binom{u-1}{v-1} - \binom{\frac{u}{p}-1}{\frac{v}{p}-1} \equiv 0 \pmod{p^{\beta}}. \qquad (2)$$
Put $w = u - v$. Then
$$\begin{aligned} \binom{u-1}{v-1} &= \frac{\prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r+w) \cdot \prod_{1 \le y \le \frac{v}{p}-1} (yp+w)}{\prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r) \cdot \prod_{1 \le y \le \frac{v}{p}-1} (yp)} \\ &= \frac{\prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r+w)}{\prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r)} \cdot \binom{\frac{u}{p}-1}{\frac{v}{p}-1}. \end{aligned}$$

Since $w$ is divisible by $p^\beta$, we get
$$\begin{aligned} & \left( \begin{matrix} u-1 \\ v-1 \end{matrix} \right) \prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r) \\ & = \left( \begin{matrix} \frac{u}{p}-1 \\ \frac{v}{p}-1 \end{matrix} \right) \prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r+w) \\ & = \left( \begin{matrix} \frac{u}{p}-1 \\ \frac{v}{p}-1 \end{matrix} \right) \prod_{0 \le x \le \frac{v}{p}-1, 1 \le r \le p-1} (xp+r) \pmod{p^\beta}, \end{aligned}$$
So (2) holds, and we complete the proof of the lemma.
Another proof of the lemma: We will use the following fact. Let $X$ be a finite set, and let $h: X \to X$ be a map such that $h^{(a)} = \text{Id}_X$. Under the action of $h$, $X$ is divided into some orbits. Each orbit looks like $\{x, h(x), h^{(2)}(x), \dots, h^{(l)}(x) = x\}$, where $l$ is the smallest positive integer such that $h^{(l)}(x) = x$; we call $l$ the length of the orbit. Since $h^{(a)} = \text{Id}_X$, the length $l$ of every orbit is a divisor of $a$. For every divisor $l$ of $n$, let $N(l)$ be the number of orbits with length $l$. For every positive integer $k|a$, let
$$m(k) = \#\{x \in X : h^{(k)}(x) = x\},$$
then $m(k) = \sum_{l|k} N(l)l$. Therefore we get
$$\begin{aligned} \sum_{k|a} \mu(k) m\left(\frac{a}{k}\right) &= \sum_{k|a} \sum_{l|\frac{a}{k}} \mu(k) N(l) l \\ &= \sum_{l|a} N(l) l \sum_{k|\frac{a}{l}} \mu(k) \\ &= N(a) a. \end{aligned}$$
In particular, we have
$$\sum_{k|a} \mu(k) m\left(\frac{a}{k}\right) \equiv 0 \pmod{a}. \qquad (3)$$
We apply this to the following model. Let $X$ be the set of all subsets of $\mathbb{Z}/a$ of $b$ elements. Define $h: X \to X$ to be
$$h(\{y_1, \dots, y_b\}) = \{y_1 + 1, \dots, y_b + 1\}, \quad \forall \{y_1, \dots, y_b\} \in X.$$
In this model, for every divisor $k$ of $a$, we have
$$m(k) = \binom{k}{b/(a/k)}.$$
Then (3) implies that
$$\sum_{k|a} \mu(k) \binom{a/k}{b/k} \equiv 0 \pmod{a}.$$