Республиканская олимпиада по математике, 2003 год, 10 класс

Докажите, что число $C_{2p}^p - 2$ делится на $p^3$, для любого простого $p \geq 5$, где $C_{2p}^p=\frac{(2p)!}{{(p!)}^2}$.

Комментарий/решение

Докажем, что $C_{2p-1}^p-1$ делится на $p^3$, из этого напрямую будет следовать требуемое.

$$C_{2p-1}^p\equiv 1 \pmod {p^3} \iff (p+1)(p+2)\ldots(p+(p-1))\equiv (p-1)! \pmod {p^3}$$

Вынесем $1, 2, 3, \ldots, p-1$ соответственно из скобок в левой части и сократим обе части на $(p-1)!$:

$$(p-1)! \cdot (p+1) (\dfrac{p}{2}+2) \ldots (\dfrac{p}{p-1}+1) \equiv (p-1)! \pmod {p^3}$$ $$\iff (p+1)(\dfrac{p}{2}+2)\ldots(\dfrac{p}{p-1}+1)\equiv 1 \pmod {p^3}$$

Раскроем скобки:

$$(p+1)(\dfrac{p}{2}+2)\ldots(\dfrac{p}{p-1}+1)\equiv p^2 \cdot \sum_{1\le i < j \le p-1} \dfrac{1}{ij} + p\sum_{i=1}^{p-1} \dfrac{1}{i} + 1 \stackrel{?}{\equiv} 1 \pmod {p^3}$$

Осталось доказать, что

$$\sum_{1\le i < j \le p-1} \dfrac{p}{ij} + \sum_{i=1}^{p-1} \dfrac{1}{i} \equiv 0 \pmod {p^2}$$

Докажем, что $\sum_{i=1}^{p-1} \frac{1}{i} \equiv 0 \pmod{p^2}$. Сгруппировав слагаемые парами $(i, p-i)$:

$$ \sum_{i=1}^{p-1} \frac{1}{i} = \sum_{i=1}^{\frac{p-1}{2}} \left( \frac{1}{i} + \frac{1}{p-i} \right) = \sum_{i=1}^{\frac{p-1}{2}} \frac{p}{i(p-i)} \equiv -p \sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \pmod{p^2} $$

Так как $$\sum_{i=1}^{p-1} \frac{1}{i^2} \equiv \sum_{i=1}^{p-1} i^2 = \frac{(p-1)p(2p-1)}{6} \equiv 0 \pmod p$$. Отсюда:

$$ \sum_{i=1}^{p-1} \frac{1}{i} \equiv -p \cdot 0 \equiv 0 \pmod{p^2} $$

Завершим доказательство по тождеству квадрата суммы:

$$\sum_{1\le i < j \le p-1} \dfrac{1}{ij}=\dfrac{1}{2}\cdot(\sum_{i=1}^{p-1} \dfrac{1}{i})^2-\dfrac{1}{2} \cdot \sum_{i=1}^{p-1} \dfrac{1}{i^2} \equiv 0 - 0 = 0 \pmod p. \qquad \blacksquare$$