Given a positive integer $n$, let $D$ is the set of positive divisors of $n$, and let $f: D \to \mathbb{Z}$ be a function. Prove that the following are equivalent: (a) For any positive divisor $m$ of $n$, \[ n ~\Big|~ \sum_{d|m} f(d) \binom{n/d}{m/d}. \](b) For any positive divisor $k$ of $n$, \[ k ~\Big|~ \sum_{d|k} f(d). \]
Problem
Source: 2022 China TST, Test 2, P5
Tags: number theory, Divisors, binomial coefficients
Tintarn
29.03.2022 13:18
For convenience, write $g(d)=\sum_{e \mid d} f(e)$ so that $f(d)=\sum_{e \mid d} \mu\left(\frac{d}{e}\right) g(e)$ by Möbius Inversion. Then we need to prove that $k \mid g(k)$ for all $k$ iff
\[n \mid \sum_{d \mid m} \binom{n/d}{m/d} \sum_{e \mid d} \mu\left(\frac{d}{e}\right) g(e)=\sum_{e \mid m} g(e)h(m/e,n/e)\]where
\[h(m,n):=\sum_{d \mid m} \mu(d) \binom{n/d}{m/d}.\]Now clearly if we can prove that $n \mid h(m,n)$ for all $m,n$, then we see that $e \mid g(e)$ for all $e$ implies that
\[n=e \cdot \frac{n}{e} \mid g(e)h(m/e,n/e)\]for all $e$ and hence one direction follows. Conversely, if we assume the second condition and $n \mid h(m,n)$ for all $m,n$, then to prove $m \mid g(m)$ for all $m$, by induction we can assume that $n \mid g(m)h(1,n/m)=g(m) \cdot \frac{n}{m}$ and hence $m \mid g(m)$ as well.
So everything boils down to proving the claim that $n \mid h(m,n)$, in other words
\[n \mid \sum_{d \mid m} \mu(d)\binom{n/d}{m/d}.\]But by Inclusion-Exclusion, the RHS counts the number of choices of a set of $m$ elements from $n$ objects in a circle such that the $n$ translates of this set are all distinct. But these sets of course fall into orbits of size $n$, so their number is clearly divisible by $n$, as desired. Done!
CANBANKAN
29.03.2022 20:27
Let $g(k)=\sum\limits_{d\mid k} f(d)$.
By PIE/Mobius inversion, $f(k)=\sum\limits_{d\mid k} \mu(\frac kd) f(d)$
Suppose (b) holds We first prove if $k\mid g(k)$ for all $k\mid n$ then $n\mid \sum\limits_{d\mid m} f(d) \binom{n/d}{m/d}$ for all $m\mid n$.
To prove this, we rewrite it as $m\mid \sum\limits_{d\mid m} f(d) \binom{n/d-1}{m/d-1} = \sum\limits_{d\mid m} \sum\limits_{k\mid d} g(k) \mu(\frac dk) \binom{n/d-1}{m/d-1} = \sum\limits_{k\mid m} g(k) \sum\limits_{k\mid d\mid m} \mu(\frac dk) \binom{n/d-1}{m/d-1}$
Therefore, if I show $\frac mk \mid \sum\limits_{k\mid d\mid m} \mu(\frac dk) \binom{n/d-1}{m/d-1}$ for all $k|m|n$, I am done since each term in the sum is a multiple of $m$.
Let $x=\frac mk$, $d'=\frac dk$ and $y=\frac nm$, then $d'$ ranges over all divisors of $x$.
We are trying to show $x\mid \sum\limits_{d'\mid x} \mu(d') \binom{yx/d'-1}{x/d'-1}$
Let $\nu_p(x)=e$, then note if $\mu(d')\ne 0$ then $\nu_p(d')\in \{0,1\}$. Therefore, we can group the right sum into groups of the form $(\binom{yp^et-1}{p^et-1}-\binom{yp^{e-1}t-1}{p^{e-1}t-1})$. I claim each of them is divisible by $p^e$.
Note $\binom{yp^et-1}{p^et-1} = \prod\limits_{j=1}^{p^et-1} (\frac{yp^et}{j}-1) = \prod\limits_{p\nmid j, 1\le j\le p^et-1} (\frac{yp^et}{j}-1) \cdot \prod\limits_{j=1}^{p^{e-1}t-1} (\frac{yp^et}{pj}-1)=\binom{yp^{e-1}t-1}{p^{e-1}t-1}) \cdot \prod\limits_{p\nmid j, 1\le j\le p^et-1} (\frac{yp^et-1}{j}-1)$
So we want to show $p^e\mid \prod\limits_{p\nmid j, 1\le j\le p^et-1} (\frac{yp^et-1}{j}-1)-1$. Note the 1's cancel out, and I need to prove $p^e \sum\limits_{p\nmid j, 1\le j\le p^et-1} \frac 1j$ is at least $p^e$ in $\nu_p$, which is obvious.
Suppose (b) doesn't hold , then let $k$ be the smallest integer such that $k\nmid g(k)$. We want to show $m\nmid \sum\limits_{k\mid n} g(k) \sum\limits_{k\mid d\mid m} \mu(\frac dk) \binom{n/d-1}{m/d-1}$. To prove this, we've proven if $k\mid g(k)$ then the $k$ contribution is 0 mod $m$, so $\sum\limits_{k\mid m} g(k) \sum\limits_{k\mid d\mid m} \mu(\frac dk) \binom{n/d-1}{m/d-1} \equiv g(m) \sum\limits_{m\mid d\mid m} \mu(\frac dm) \binom{n/d-1}{m/d-1} = g(m) \mu(1) \binom{n/m-1}{0} = g(m)$, as desired.
naman12
14.04.2022 19:25
Nice problem. We first claim the following: Claim. For any positive integers $m$ and $k$, we have \[m\left|~\sum_{d\mid m}\mu\left(\frac md\right)\binom{kd-1}{d-1}\right.\]where $\mu(j)$ is the classic mobs function. Proof. Consider any prime $p\mid m$, and suppose $\nu_p(m)=\alpha\geq 1$. Note that the only $d$ that show up in the sum are ones with $\nu_p(d)\in\{\alpha,\alpha-1\}$, as otherwise $p^2\mid m/d$ and thus $\mu(m/d)=0$. If we let $m=p^\alpha n$, the above sum is \[\sum_{d\mid n}\mu\left(\frac nd\right)\left(\binom{kdp^\alpha-1}{dp^\alpha-1}-\binom{kdp^{\alpha-1}-1}{dp^{\alpha-1}-1}\right)\]Thus it suffices to show \[\binom{kdp^\alpha-1}{dp^\alpha-1}\equiv\binom{kdp^{\alpha-1}-1}{dp^{\alpha-1}-1}\pmod{p^\alpha}\]Note that \begin{align*} \binom{kdp^\alpha-1}{dp^\alpha-1}&=\prod_{k=1}^{dp^\alpha-1}\frac{kdp^\alpha-1-k}{dp^\alpha-1-k}\\ &=\prod_{k=1}^{dp^{\alpha-1}-1}\frac{kdp^\alpha-1-kp}{dp^\alpha-1-kp}\cdot\prod_{k=0}^{dp^{\alpha-1}-1}\prod_{\ell=1}^{p-1}\frac{kdp^\alpha-1-kp-\ell}{dp^\alpha-1-kp-\ell}\\ &\equiv \prod_{k=1}^{dp^{\alpha-1}-1}\frac{kdp^{\alpha-1}-1-k}{dp^{\alpha-1}-1-k}\cdot\prod_{k=0}^{dp^{\alpha-1}-1}\prod_{\ell=1}^{p-1}1\\ &=\binom{kdp^{\alpha-1}-1}{dp^{\alpha-1}-1}\pmod{p^\alpha} \end{align*}completing the proof. $\square$ Now, we let \[g(k)=\sum_{d\mid k}f(k)\]and by the Mobius Inversion Formula, we get \[f(k)=\sum_{d\mid k}\mu\left(\frac kd\right)g(k)\]Thus, we know \begin{align*} \sum_{d\mid m}f(d)\binom{n/d}{m/d}&=\sum_{d\mid m}\binom{n/d}{m/d}\sum_{k\mid d}\mu\left(\frac dk\right)g(k)\\ &=\sum_{k\mid m}g(k)\sum_{d\mid m/k}\mu(d)\binom{n/dk}{m/dk}\\ &=\frac nm\sum_{k\mid m}g(k)\sum_{d\mid m/k}\mu(d)\binom{n/dk-1}{m/dk-1} \end{align*}Note that by the claim, the second sum is divisible by $m/k$. Now, if (b) holds, then literal substitution shows \[\frac nm\cdot g(k)\cdot \sum_{d\mid m/k}\mu(d)\binom{n/dk-1}{m/dk-1}\equiv 0\pmod n\]as $k\mid g(k)$ and $m/k$ divides the sum. On the contrary, if (a) holds, assume (b) doesn't and let $m$ be the smallest divisor of $n$ that doesn't satisfy (b). Then, we know \[n\mid\frac nm\sum_{k\mid m}g(k)\sum_{d\mid m/k}\mu(d)\binom{n/dk-1}{m/dk-1}\]All other than the last term are divisible by $n$ for the same reason as above, and the last term is \[\frac nmg(m)\]Thus, we must have $m\mid g(m)$, a contradiction. This completes the proof.
Joider
18.07.2023 08:47
Can anyone explain how $\binom{n/d}{m/d}=(\binom{yp^et-1}{p^et-1}-\binom{yp^{e-1}t-1}{p^{e-1}t-1})$
Joider
24.07.2023 17:53
Joider wrote: Can anyone explain how $\binom{n/d}{m/d}=(\binom{yp^et-1}{p^et-1}-\binom{yp^{e-1}t-1}{p^{e-1}t-1})$ Friends can anyone explain that there is any relation between these two terms??