Сумма

[Руст]

Еще одна задача:

Let p be a prime congruent to 7 modulo 8. Prove that :

$$\sum\limits_{k=1}^{p} \left\lfloor\frac{k^2+k}{p}\right\rfloor=\frac{2p^2+3p+7}{6}.$$

[Sonic86]

Получилось найти только $\sum\limits_{k=1}^p\lfloor\frac{k^2}{p}\rfloor$ для $p\equiv 1\pmod{4}$, а обобщить рассуждение не получается. Можете намекнуть?

[Руст]

Попробуйте дополнить до полного квадрата.

[Sonic86]

(Оффтоп)

Руст в сообщении #825742 писал(а):

Попробуйте дополнить до полного квадрата.

Пробовал, и по-разному, мне чего-то другого существенно не хватает. Я могу вычислить $\sum\limits_{k=1}^{p-1}\left\{\frac{k^2}{p}\right\}$ при $p\equiv 1\pmod{4}$ потому, что при таком условии есть корень из $-1$ в поле и тогда все квадраты разбиваются на пары вида $y,p-y$ при $p>3$ и тогда сумма легко находится. А в данном случае такого нет: значения $\left\{\frac{k^2+k}{p}\right\}$ не образуют пар $y,p-y$, и с условием это никак не сходится. Условие явно точное, значит выбор $p\equiv -1\pmod{8}$ должен давать 2 каких-то факта, например, что $2$ - квадратичный вычет и еще какой-то. Но как их суюда прикрутить - непонятно.
Значения $\left\{\frac{(2k+1)^2}{4p}\right\}$ точно так же образуют симметричные пары $y,y$, а не $y,p-y$ - это их свойство сохраняется при переходе от исходного выражения к ним.
Можно перейти от $\left\{\frac{k^2+k}{p}\right\}$ к $\left\{\frac{k^2-2^{-2}}{p}\right\}$, но чему равна $\sum\limits_{k=1}^{p-1}\left\{\frac{k^2}{p}\right\}$ при $p\equiv -1\pmod{8}$ - еще более непонятно.
В общем, не вижу я

[Руст]

Я сейчас не имею времени для полного решения.
Обозначим через $g(k)=\{\frac{k^2+k}{p}\}$ и выразим сумму целых частей как разницу
всей суммы $ \sum_{k=1}^p\frac{k^2+k}{p}=\frac{(p+1)(2p+1)}{6}+\frac{(p+1)}{2}=\frac{p^2+3p+2}{3}$.
Достаточно доказать, что
$\sum_{k=1}^{p} g(k)=\frac{p^2+3p+2}{3}-\frac{2p^2+3p+7}{6}=\frac{p-1}{2}.$
Рассмотрим
$g(\frac{p-1}{2}+k)=\{\frac{(\frac{p-1}{2}+k)(\frac{p+1}{2}+k)}{p}\}=\{\frac{3p-1}{4p}+\frac{k^2}{p}\}=\{\frac 34+\frac{k^2}{p}\}-\frac{1}{4p}$.
Здесь учли, что $p=3\mod 4$ и дробная часть не обращается в нуль.
Из-за периодичности функции $g(k)$ мы можем суммировать по любому полному периоду. В частности мы можем взять сумму $f(k)=\{\frac 34 +\frac{k^2}{p}\}$ по полному периоду и вычесть $\frac 14$.
Тут надо учесть что и для $f(k)$ можно суммировать по любому полному периоду и если $k$ проходит по полному периоду, то и $2k$ так же проходит по полному периоду.
Надеюсь это поможет решать задачу.

[Руст]

Попробую привести свое решение (пока не знаю, приведет ли к доказательству формулы):

$$S=\sum_{k=1}^p[\frac{k^2+k}{p}]=\sum_{k=1}^p\frac{k^2+k}{p}-\sum_{k=1}^p\{\frac{k^2+k}{p}\}=\frac{(p+1)(p+2)}{3}-\sum_{k=1}^p\{\frac{((p-1)/2+k)^2+(p-1)/2+k}{p}\}.$$

Здесь использовал сдвиг для суммирования (по полному периоду). Учтем, что члены в последней сумме есть $\{\frac{\frac{p^2-1}{4}+pk+k^2}{p}\}=\{\frac 34 +\frac kp\}-\frac{1}{4p}.$
Таким образом

$$S=\frac{(p+1)(p+2)}{3}-(\frac 34 -\frac 14)-\sum_{k=1}^{p-1}((\frac kp)+1)\{\frac 34+\frac{k}{p}\}=\frac{p^2+3p+2}{3}-\frac 12-\sum_{k=1}^{p-1}\{\frac 34+\frac kp\}-\sum_{k=1}^{p-1}(\frac kp)\{\frac 34+\frac kp\}=$$ $$=\frac{p^2+3p+2}{3}-\frac 12-\sum_{k=1}^{p-1}\frac kp -\frac 34 \frac{p-3}{4}+\frac 14 (p-1-\frac{p-3}{4})-\sum_{k=1}^{p-1}(\frac kp)\{\frac 34 +\frac kp\}=\frac{2p^2+3p+7}{6}-\sum_{k=1}^{p-1}(\frac kp)\{\frac 34+\frac kp\}.$$

Остается показать, что последняя сумма равна нулю (здесь $(\frac kp)$ - символ Лежандра).

$$S_1=\sum_{k=1}^{p-1}(\frac kp)\{\frac 34+\frac kp\}=\frac 34 \sum_{0<k<p/4}(\frac kp)-\frac 14\sum_{p/4<k<p}(\frac kp)+\sum_{k=1}^{p-1}(\frac kp)\frac kp=\sum_{0<k<p/4}(\frac kp)+\sum_{k=1}^{p-1}(\frac kp)\frac kp=X(0,\frac 14)+Y(0,1).$$

Здесь использовал, что $\sum_{k=1}^{p-1}(\frac kp)=0$ и обозначения

$$X(a,b)=\sum_{ap<k<bp}(\frac kp), Y(a,b)=\sum_{ap<k<bp}(\frac kp)\frac kp.$$

Тогда

$$S_1=X(0,\frac 14)+\sum_{k=1}^{(p-1)/2}((\frac kp)\frac kp +(\frac{p-k}{p})\frac{p-k}{p})=2Y(0,\frac 12)+X(0,\frac 14)-X(0,\frac 12)=2Y(0,\frac 12)-X(\frac 14,\frac 12).$$

Теперь используем то, что 2 квадратичный вычет, переходя к суммированию по четным и нечетным элементам в $Y(0,\frac 12)=\sum_{0<k<p/2}(\frac kp)\frac kp$.

$$Y(0,\frac 12)=\sum_{0<k<p/4}(\frac{2k}{p})\frac{2k}{p}+\sum_{p/4<k<p/2}(\frac{p-2k}{p})\frac{p-2k}{p}=2Y(0,\frac 12)-X(\frac 14,\frac 12).$$

Подставляя полученное отсюда $Y(0,\frac 12)=X(\frac 14, \frac 12)$ в $S_1$ получаем:
$S_1=X(\frac 14 , \frac 12).$
Докажем теперь некоторые свойства сумм X.
Симметрия $X(a,b)=-X(1-b,1-a)$ получается из того, что $(\frac{-1}{p})=-1$.
Разделим на четные и нечетные и используем, что 2 квадратичный вычет.
$X(a,b)=X(\frac a2,\frac b2)+\sum_{k-odd}(\frac kp)=X(\frac a2,\frac b2)-X(\frac{1-b}{2},\frac{1-a}{2}).$
Подставляя сюда $a=0,b=\frac 12$ получаем
$X(0,\frac 12)=X(0,\frac 14)-X(\frac 14 ,\frac 12)=X(0,\frac 12)-2X(\frac 14, \frac 12)$, т.е. $X(\frac 14, \frac 12)=0$ и тем самым $S_1=0$.