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
29.03.2022 13:18
29.03.2022 20:27
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.
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})$
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??