Сумма дробей по простому модулю

[nnosipov]

(Туймаада-2012) Пусть $p$ --- простое число вида $4k+3$. Сумму дробей

$$ \frac{1}{0^2+1}+\frac{1}{1^2+1}+\ldots+\frac{1}{(p-1)^2+1} $$

представили в виде одной дроби $m/n$. Докажите, что $2m-n$ делится на $p$.

Эта несложная, но содержательная задача интересна тем, что допускает несколько (по крайней мере, четыре) разных способов решения. Предлагаю всем желающим поупражняться в решении этой задачи.

[nnosipov]

Как ни странно, самое короткое решение этой задачи достигается школьными средствами, без какой бы то ни было "высшей" математики. Обычно бывает наоборот.

[Sonic86]

$S:=\sum\limits_{k=0}^{p-1}\frac{1}{k^2+1}$
$p\mid 2m-n\Leftrightarrow 2S\equiv 1\pmod{p}$
$2S=2+\sum\limits_{k=1}^{p-1}\frac{2}{k^2+1}$
$k\neq 0\Rightarrow\frac{2}{k^2+1}=\frac{2(1-k^2+k^4-...+k^{p-3})}{1+k^{p-1}}\equiv 1-k^2+k^4-...+k^{p-3}\pmod p$ (это тут главное)
$2S\equiv 2+\sum\limits_{k=1}^{p-1}1-k^2+k^4-...+k^{p-3}\equiv 2+(p-1)\equiv 1\pmod p$, поскольку при $p-1\nmid a\Rightarrow \sum\limits_{k=1}^{p-1}k^a\equiv 0\pmod{p}$.

Это школьный метод? Хотелось бы увидеть все варианты, поскольку такое ощущение, что я не все понял.

[nnosipov]

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

Это школьный метод?

Нет, это один из не совсем школьных У Вас получилось даже проще, чем у меня (я не заметил то тождество с $k$ и вместо него использовал более сложное тождество). Но школьный способ ещё проще. Кроме него, есть ещё два, где используются многочлены (над конечным полем, естественно). Небольшой хинт: логарифмическая производная.

[Sonic86]

$\sum\limits_{k=0}^{p-1}\frac{1}{k^2+1}=\frac{m}{n}.$
Поскольку $p\nmid m,n$, то дробь можно не сокращать, и считать, что $n=\prod\limits_{k=0}^{p-1}(k^2+1), m=\prod\limits_{k=0}^{p-1}(k^2+1)\sum\limits_{k=0}^{p-1}\frac{1}{k^2+1}$. Считаем вычеты:
$n=\prod\limits_{k=0}^{p-1}(k^2+1)=\sum\limits_{k=0}^{p-1}\sigma_k(\mathbb{Z}_p^2)$, здесь $\sigma_k(M)$ - $k$-й элементарный симметрический многочлен на мультимножестве $M$. Поскольку $t\to g^2t$ - биекция $\mathbb{Z}_p^2$, то $\sigma_k(\mathbb{Z}_p^2)\equiv\sigma_k(g^2\mathbb{Z}_p^2)\equiv g^{2k}\sigma_k(\mathbb{Z}_p^2)\pmod p$, то при $p-1 \nmid 2k$ $\sigma_k(\mathbb{Z}_p^2)\equiv 0\pmod p$, и тогда $n\equiv 1+\sigma_{\frac{p-1}{2}}(\mathbb{Z}_p^2)+\sigma_{p-1}(\mathbb{Z}_p^2)\pmod p$. Последнее слагаемое - это $(p-1)!^2\equiv 1\pmod p$, а промежуточное слагаемое $\sigma_{\frac{p-1}{2}}(\mathbb{Z}_p^2)\equiv -1\pmod p$ (пока не понял, почему). Так что $n\equiv 1\pmod p$.
$2m$ пока у меня не считается.

Про логарифмическую производную не смог ничего придумать

[nnosipov]

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

Так что $n\equiv 1\pmod p$.

На самом деле $n \equiv 4 \pmod{p}$. Здесь можно считать сразу весь многочлен $\prod_{k=0}^{p-1} (x-k^2-1)$. Но лучше это делать не по-честному.

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

Про логарифмическую производную не смог ничего придумать

Не знаю почему, но меня как-то сразу потянуло попользоваться формулой

$$ \sum_{k=1}^n \frac{1}{x-a_k}=\frac{P'(x)}{P(x)}, $$

где $P(x)=\prod_{k=1}^n (x-a_k)$. В результате получилось самое нешкольное решение.

[Mathusic]

$x^2=-1$ не имеет корней над $\mathbb{Z}_p$ ($p=4k+3$, а значит, $-1$ -- невычет). Тогда присоединим корень этого уравнения $i$ к полю $\mathbb{Z}_p$ и рассмотрим над ним сумму

$$S=1+\frac{1}{1^2+1}+\ldots+\frac{1}{(p-1)^2+1}$$

(хотим, чтобы было $S=\frac{1}{2}$)
Имеем

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

Далее,

$$S = 1+\frac{1}{i}\sum_{k=1}^{p-1}\frac{1}{(k-i)}=1-\frac{1}{i}\sum_{k=1}^{p-1}\frac{1}{(i-k)}=1-\frac1i\frac{P'(i)}{P(i)}$$

где $P(x) = (x-1)(x-2) \ldots (x-(p-1)).$ А так как $P(x)=(x^{p-1}-1),$ то $P'(x)=-x^{p-2}.$
Тогда

$$S=1-\frac1i\left(\frac{-i^{4k+1}}{i^{4k+2}-1}\right)=1-\frac1i\left(\frac{-i}{-2}\right)=\frac{1}{2}$$

[nnosipov]

Хорошо, одно решение с многочленами найдено. Mathusic, а зачем Вы в сумме единичку выделили?

[Mathusic]

nnosipov в сообщении #603005 писал(а):

а зачем Вы в сумме единичку выделили?

Кстати, да. Можно было не выделять. Просто в других вариантах она "мешалась", поэтому и начал расписывать именно так

[Mathusic]

Вот например, ещё один способ, кстати: немного похож на первый от Sonic86.

Пусть $\mathbb{Z}_p(2)$ - множество всех квадратичных вычетов над $\mathbb{Z}_p,$ $p=4k+3.$
Тогда

$$S=1+\frac{1}{1^2+1}+\ldots+\frac{1}{(p-1)^2+1}=1+\sum_{x \in \mathbb{Z}_p(2)}\frac{2}{(x+1)}=1+\sum_{x=1}^{p-2}{\frac{x^{\frac{p-1}2}+1}{(x+1)}}=$$

$$=1+\sum_{x=1}^{p-2}{\frac{x^{2k+1}+1}{(x+1)}}=1+\sum_{x=1}^{p-2}{(x^{2k}-x^{2k-1}+x^{2k-2}- \ldots - x +1)}=\left[ \dots \right]=\frac{1}{2}$$

Несложные вычисления опущены.

[nnosipov]

И это тоже хорошо! По моим подсчётам, это уже пятый способ.

[sup]

1. Заметим, что
$\frac{1}{a^2 + 1}+\frac{1}{b^2 + 1} = 1 - \frac{(ab)^2-1}{(a^2 + 1)(b^2 + 1)}$
После этого группируем слагаемые так, чтобы $ab \equiv 1 (\mod p)$
Получим
$S \equiv (1 + 1/2 +(p-3)/2 + 1/2)(\mod p) \equiv (p+1)/2 (\mod p)$
2. Рассмотрим сумму
$S_1 = \sum \limits_{a=1}^{p-1} \frac{1}{a^2 + 1}$
Очевидно, что для любого $1 \leq b <p$
$S_1 \equiv \sum \limits_{a=1}^{p-1} \frac{b^2}{a^2 + b^2}(\mod p)$
Суммируя по всем таким $b$, получим
$(p-1)S_1 \equiv \sum \limits_{b=1}^{p-1}\sum \limits_{a=1}^{p-1} \frac{b^2}{a^2 + b^2}(\mod p) = (p-1)^2 - (p-1)\sum \limits_{b=1}^{p-1} \frac{b^2}{a^2 + b^2}$
Значит $S_1 \equiv ((p-1)/2)(\mod p)$
3. Положим $P(z)=\prod \limits_{a=1}^{p-1} (z+a^2)$
Ясно, что $n=P(1)$ и $m=n + P'(1)$. Честно раскрываем скобки и дифференцируем. Получим
$P'(z)=(p-1)z^{p-2} + (p-2)z^{p-3}\sum \limits_{a} a^2 + (p-3)z^{p-4}\sum \limits_{a_1, a_2}a_1^2a_1^2 + \dots $
Ну а теперь надо заметить, что $\prod \limits_{a=1}^{p-1} a^2 \equiv 1 (\mod p)$ (тут не нужна даже теорема Вильсона). Поэтому сумма квадратов сравнима с суммой всех $(p-2)$-произведений. Сумма парных произведений сравнима с суммой всех $(p-3)$-произведений и тд. Группируя эти слагаемые, легко получить, что $P'(1) \equiv \frac {p-1}{2}P(1) (\mod p)$.

-- Пн авг 06, 2012 10:25:24 --

Кстати, в последнем варианте вполне можно обойтись без дифференцирования. Нужно просто привести все дроби к общему знаменателю.

[Mathusic]

sup в сообщении #603322 писал(а):

1. Заметим, что
$\frac{1}{a^2 + 1}+\frac{1}{b^2 + 1} = 1 - \frac{(ab)^2-1}{(a^2 + 1)(b^2 + 1)}$
После этого группируем слагаемые так, чтобы $ab \equiv 1 (\mod p)$
Получим
$S \equiv (1 + 1/2 +(p-3)/2 + 1/2)(\mod p) \equiv (p+1)/2 (\mod p)$

Красиво!
Решение, наверное, можно отнести к школьному? (даже МТФ не используется, как, например, в самом первом доказательстве, только парочку соображений из арифметики остатков)
Может быть, это оно самое?

-- Пн авг 06, 2012 12:24:42 --

sup в сообщении #603322 писал(а):

1. Заметим, что
2. Рассмотрим сумму
$S_1 = \sum \limits_{a=1}^{p-1} \frac{1}{a^2 + 1}$
Очевидно, что для любого $1 \leq b <p$
$S_1 \equiv \sum \limits_{a=1}^{p-1} \frac{b^2}{a^2 + b^2}(\mod p)$

Кстати, так как для всех $1 \leq b <p$

$$S_1=\sum \limits_{a=1}^{p-1} \frac{1}{a^2 + 1}=\sum \limits_{a=1}^{p-1} \frac{1}{(\frac{a}{b})^2 + 1}=\sum \limits_{a=1}^{p-1} \frac{1}{(\frac{b}{a})^2 + 1}$$

То

$$2S_1=\sum \limits_{a=1}^{p-1} \frac{a^2}{a^2+b^2}+\sum \limits_{a=1}^{p-1} \frac{b^2}{a^2+b^2}=p-1$$

Это уже какой способ по счёту?

[Mathusic]

Хотя так даже проще $\displaystyle \sum \limits_{a=1}^{p-1} \frac{1}{a^2 + 1}=\sum \limits_{a=1}^{p-1} \frac{1}{(\frac{1}{a})^2 + 1}=\sum \limits_{a=1}^{p-1} \frac{a^2}{a^2 + 1}$
(То есть $b=1$, значит существует $(p-1)$ способов доказательства )

[Sonic86]

Mathusic, красивое решение, спасибо большое