Prove that for every prime number $p\ge5$, (a) $p^3$ divides $\binom{2p}p-2$; (b) $p^3$ divides $\binom{kp}p-k$ for every natural number $k$.
Problem
Source: Bulgaria 1991 P3
Tags: number theory
03.06.2021 05:15
I will do part (b), the most general version. In what follows, all arithmetic modulo $p$. Since \[ \binom{kp}{p} = k\cdot\frac{(kp-1)\cdots(kp-p+1)}{(p-1)!}, \]it suffices to show \[ \frac{(kp-1)(kp-2)\cdots(kp-p+1)}{(p-1)!}\equiv 1\Leftrightarrow P(kp)\equiv (p-1)!\pmod{p^3}, \]where \[ P(x)=(x-1)(x-2)\cdots(x-p+1). \]Note that $\textstyle P(x) = (p-1)! +\alpha_1 x+\alpha_2 x^2+\sum_{k\ge 3}\alpha_k x^k$ for some coefficients $\alpha_i\in\mathbb{Z}$, $i\ge 1$ with \[ \alpha_1 = -(p-1)!\sum_{1\le j\le p-1}\frac1j \qquad\text{and}\qquad \alpha_2 = (p-1)! \sum_{1\le i<j\le p-1}\frac{1}{ij}. \]Note that $\textstyle\sum_{k\ge 3}\alpha_k x^k\equiv 0\pmod{p^3}$ for $x=kp$. Hence, it suffices to show \[ \alpha_1 kp + \alpha_2 k^2p^2\equiv 0\pmod{p^3}, \]that is, it suffices to verify \[ \alpha_1 k +\alpha_2 k^2 p\equiv 0\pmod{p^2}. \]Now, observe that \[ \sum_{1\le i\le p-1}\frac1i = \sum_{1\le i\le \frac{p-1}{2}} \left(\frac1i+\frac{1}{p-i}\right) = p\sum_{1\le i\le \frac{p-1}{2}} \frac{1}{i(p-i)}\equiv 0\pmod{p}. \]Furthermore, \[ \alpha_2 = \frac12 \left(\sum_{1\le i\le p-1}\frac1i\right)^2 - \frac12\sum_{1\le i\le p-1}\frac{1}{i^2} \equiv 0\pmod{p}, \]since \[ \sum_{1\le i\le p-1}\frac{1}{i^2}\equiv \sum_{1\le i\le p-1}i^2 = \frac{p(p-1)(2p-1)}{6}\equiv 0\pmod{p} \]for $p>3$. These together yield $\alpha_2k^2 p\equiv 0\pmod{p^2}$, and it remains to show $p^2\mid \alpha_1$. Again, inspecting above, it suffices to show \[ p^2 \mid \alpha_1 = \sum_{1\le i\le \frac{p-1}{2}} \left(\frac{1}{i} + \frac{1}{p-i}\right) = p\sum_{1\le i\le \frac{p-1}{2}}\frac{1}{i(p-i)}, \]which boils down proving \[ \sum_{1\le i\le \frac{p-1}{2}}\frac{1}{i(p-i)}\equiv -\sum_{1\le i\le \frac{p-1}{2}} \frac{1}{i^2} \equiv 0\pmod{p}. \]To show this final claim, note that $i\mapsto i^{-1}$ is injective modulo $p$, hence the sum traces through all quadratic residues. That is, \[ \sum_{1\le i\le \frac{p-1}{2}} \frac{1}{i^2} \equiv \sum_{1\le i\le \frac{p-1}{2}} i^2 \equiv \frac{p(p-1)(p+1)}{24}, \]which is clearly divisible by $p$ for $p>3$. This completes the proof.