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

Даны нечетные натуральные числа $m > 1$, $k$ и простое число $p$ такое, что $p > mk+1$. Докажите, что сумма $$(C_k^k)^m+(C_{k+1}^k)^m+ \ldots +(C_{p-1}^k)^m \quad \text{делится на} \quad p^2.$$ Здесь $C_n^k=\frac{n!}{k!(n-k)!}$ — биномиальный коэффициент. ( Д. Елиусизов )

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

Решение: Поскольку $gcd(p,k!)=1,$ то достаточно доказать делимость

$$p^2\mid P(k)^m+\ldots+P(p-1)^m,$$

где $P(n)=n(n-1)\cdots(n-k+1)$ $-$ многочлен степени $k.$ Определим многочлен $Q\in\mathbb Z[x]$ след. образом

$$Q(x)=P(x)+P(p+k-x-1).$$

Свойство: Все коэффициенты $Q$ кратны $p.$

Доказательство: Здесь будем рассматривать многочлены над полем $\mathbb F_p.$

Легко понять, что

$Q(x)=P(x)+P(p+k-1-x)=P(x)+P(k-1-x)=0$ для $\forall x\in \mathbb Z.$

Отсюда легко видеть, что все коэффициенты $Q$ кратны $p,$ то есть $Q(x)=pQ_1(x),$ где $Q_1\in\mathbb Z[x].\quad\blacksquare$

Заметим, что

$$P(x)^m+P(p+k-1-x)^m=\bigg(P(x)+P(p+k-1-x)\bigg)Q_2(x)=Q(x)Q_2(x)=pR(x),$$

где $R=Q_1Q_2\in\mathbb Z[x],$ при этом $deg (R) \le mk < p-1.$ Откуда

$$2\sum_{x=k}^{p-1} P(x)^m = p\sum_{x=k}^{p-1}R(x),$$

поэтому достаточно доказать, что $p\mid\sum_{x=k}^{p-1}R(x).$ Заметим, что $p\mid P(p+k-1-x)$ и $P(x)=0,$ следовательно $p\mid R(x),$ для $\forall x\in\{1,\ldots,k-1\}.$

Осталось доказать, что $$p\mid\sum_{x=1}^{p-1}R(x),$$ что верно, так как $deg(R)<p-1.$