Сравнение по модулю p^3

[Sonic86]

Докажите или опровергните, что для простых $p \geq 5$ верно $\sum\limits_{k=0}^p C^k_p k^p \equiv 0 (mod p^3)$.
$C^k_p$ - биномиальный коэффициент.

Для квадрата я нашел, для куба не могу, проверил до 19 - верно. Сложная задача или нет - не знаю.

[Полосин]

$ S=\sum\limits_{k=0}^p C^k_p k^p=\sum\limits_{k=0}^p C^k_p (p-k)^p, (p-k)^p= (-k)^p+p^2(-k)^{p-1}+p^3(...). $
Так как $p$ - нечетное, то $ S=-S+p^2T\ (mod\ p^3), T=\sum\limits_{k=0}^p C^k_p k^{p-1}. $
Если $p$ - простое, то все биномиальные коэффициенты, кроме первого и последнего, делятся на $p$, следовательно, $T$ тоже делится на $p$, следовательно, $S$ делится на $p^3$.

[ИСН]

Полосин в сообщении #228433 писал(а):

$...(p-k)^p= (-k)^p+p^2(-k)^{p-1}+...$

Узкое место здесь.

-- Пн, 2009-07-13, 19:14 --

А, нет, торможу - всё правильно! Одно p из скобок, другое из биномиального коэффициента.

[venco]

По модулю $p^3$:
$\sum\limits_{k=0}^p C^k_p k^p = \sum\limits_{k=1}^{p-1} C^k_p k^p = \sum\limits_{k=1}^{\frac{p-1}2} C^k_p (k^p+(p-k)^p)$
Известно, что для простых $p$ $C^k_p \equiv 0\ mod\ p$.
Покажем также, что $k^p+(p-k)^p \equiv 0\ mod\ p^2$:
$k^p+(p-k)^p = k^p + p^p - C^1_p p^{p-1} k + ... + C^{p-1}_p p k^{p-1} - k^p =$
$p^p - C^1_p p^{p-1} k + ... + C^{p-1}_p p k^{p-1} \equiv 0\ mod\ p^2$, т.к. все члены суммы делятся на $p^2$.

[age]

Sonic86
Т.к. и $C_p^k\div p$ и $p^p\div p^3$, то данное утверждение равноценно:
$\sum\limits_{k=0}^{p-1} k^p \equiv 0\mod p^2$
Этот ряд содержит ровно $p-1=2m$ членов:
$1^p+2^p+...+(p-2)^p+(p-1)^p$.
Тогда его можно представить:
$1^p+2^p+...+(p-2)^p+(p-1)^p=((p-1)^p+1^p)+((p-2)^p+2^p)+...$, где количество слагаемых в скобках будет $m$.
Рассмотрим произвольное слагаемое:
$((p-k)^p+k^p)=(p-k+k)C=p\cdot C$, где $C$ - полином $p$-ой степени.
Известно, что для любого полинома простой степени $p$ $x^p+y^p$ если $x+y\div p$, то $x^p+y^p\div p^2$.
Откуда все слагаемые $((p-k)^p+k^p)\div p^2$.

[Sonic86]

Спасибо, хорошие решения, жалко сам не допер - тупею...

[venco]

Мой железный друг говорит, что равенство справедливо если $p$ нечётно, или является степенью двойки начиная с $16$, и не выполняется в остальных случаях.

[Sonic86]

venco писал(а):

Мой железный друг говорит, что равенство справедливо если $p$ нечётно, или является степенью двойки начиная с $16$, и не выполняется в остальных случаях.

Ух ты! Он это доказал?! это был Maple?
Можно обобщить и повторить рассуждения Полосина:
$n$ - нечетно
$S=\sum\limits_{k=0}^n C^k_nk^n \equiv 0 (mod n^3)$?
$S=\sum\limits_{k=0}^n C^k_n(n-k)^n$
1. $n$ - нечетно, $n \geq n_0$
$(n-k)^n \equiv -(k^n-C^1_nnk^{n-1}+C^2_nn^2k^{n-2}) \equiv -2(k^n-n^2k^{n-1})(mod n^3)$
$S \equiv -S+2n^2\sum\limits_{k=0}^nC^k_nk^{n-1}(mod n^3)$
$S \equiv 0 (mod n^3) \Leftrightarrow \sum\limits_{k=0}^nC^k_nk^{n-1} \equiv 0 (mod n)$
И так как $C^k_nk^{n-1} = nC^{k-1}_{n-1}k^{n-2}$, то $T=\sum\limits_{k=0}^n C^k_nk^{n-1} \equiv 0 (mod n)$, отсюда $S \equiv 0 (mod n^3)$
(из последнего также следует, что $(\forall n) S \equiv 0 (mod n)$).

[venco]

Sonic86 в сообщении #229892 писал(а):

venco писал(а):

Мой железный друг говорит, что равенство справедливо если $p$ нечётно, или является степенью двойки начиная с $16$, и не выполняется в остальных случаях.

Ух ты! Он это доказал?!

Не, он только не нашёл ни одного нечётного $n$, для которого модуль не равен нулю. А я прикинул, что если какие-то $C^k_n$ не делятся на $n$, то недостающий делитель найдётся в $k$, но строго доказательство не расписал.
А для чётных можете доказать?

[Руст]

Любопытная задача. И я попробовал проверить на делимость. Для нечётного n по сути здесь уже сделали за некоторой неточностью. Я обознаю через

$$S_n=\sum_{k=1}^{n-1}C_n^k k^n$$

(без последнего члена). Вычисляя поточнее получается:

$$S_n=-n^3*2^{n-2}\sum_{k=1}^{(n-1)/2}k^{n-2} \mod n^4.$$

Соответственно делимость на $n^4$ получается в некоторых случаях, например для простых Вольстенхолма.
В случае чётных n из

$$S_n=n\sum_{k=1}^{n-1}C_{n-1}^{k-1}k^{n-1}$$

получается, что $n|S_n$ всегда. Вычисление поточнее дает, что оно делится по крайней мере на $\frac{n^2}{6}$, здесь 6 в знаменателе появляется от чисел Бернулли. Можно вытащить и степень $n^3$ но выкладки громоздкие.

[Профессор Снэйп]

$$ f_0(x) = (x+1)^p = \sum_{k=0}^p C^k_p x^k $$

$$ f_0'(x) = p(x+1)^{p-1} = \sum_{k=0}^p k C^k_p x^{k-1} $$

$$ f_1(x) = xf_0'(x) = px(x+1)^{p-1} = \sum_{k=0}^p k C^k_p x^k $$

$$ f_2(x) = xf_1'(x) = \ldots = \sum_{k=0}^p k^2 C^k_p x^k $$

$$ \ldots $$

$$ f_p(x) = xf'_{p-1}(x) = \ldots = \sum_{k=0}^p k^p C^k_p x^k $$

Интересно, можно ли, идя по этому пути, что-нибудь надифференцировать, а потом подставить в $f_p(x)$ значение $x=1$?

[Руст]

Профессор Снэйп в сообщении #231410 писал(а):

$$ f_0(x) = (x+1)^p = \sum_{k=0}^p C^k_p x^k $$

$$ f_0'(x) = p(x+1)^{p-1} = \sum_{k=0}^p k C^k_p x^{k-1} $$

$$ f_1(x) = xf_0'(x) = px(x+1)^{p-1} = \sum_{k=0}^p k C^k_p x^k $$

$$ f_2(x) = xf_1'(x) = \ldots = \sum_{k=0}^p k^2 C^k_p x^k $$

$$ \ldots $$

$$ f_p(x) = xf'_{p-1}(x) = \ldots = \sum_{k=0}^p k^p C^k_p x^k $$

Интересно, можно ли, идя по этому пути, что-нибудь надифференцировать, а потом подставить в $f_p(x)$ значение $x=1$?

Можно, если брать за исходную функцию $f_0(x)=(x-1)^n$. Возьмём ваш оператор $D=x\frac{d}{dx}$ и определим n ую итерацию $f_n(x)=D^nf_0(x)=(-1)^n\sum_{k=0}^n k^nC_n^k (-x)^k$
Перейдя к переменной $t=ln x, x=1\to t=0$ получаем $D=\frac{d}{dt}$ и учитывая, что $f_n(x)=((e^t-1)^n)^{(n)}$ все члены имеют вид $b_k(e^t-1)^ke^{t(n-k)}$ и равны нулю кроме случая k=0, соответствующий коэффициент есть $n!$. Это дает известное из комбинаторики выражение $n!=(-1)^n\sum_{k=0}^nC_n^k (-1)^k k^n$.
Складывая два выражения $S_n+(-1)^n n!=2^{n+1}\sum_{k=1}^{[n/2]}C_n^{2k}k^n$ (остаются только чётные члены в двух экземплярах). Так как $ord_2(n!)\le n-1$ (равенство, когда n степень двойки), получаем $ord_2(S_n)=ord_2(n!)$.
Если $n=2^k$, то $2^{2^k-1}|S_n$ или $n^{\frac{2^k-1}{k}}|S_n. При $k=6$ получается $n^{10,5}|S_n$.