Модулярная арифметика

[nnosipov]

Пусть $p>2$ --- простое число. Для целых $a$ рассмотрим сумму

$$S(a)=\sum_{k=1}^{p-1}\frac{a^k}{k}.$$

Вычислите $S(4)+S(3)-3S(2) \bmod{p}$.

[wrest]

(ответ)

Ноль

[nnosipov]

wrest
Ответ верный. Напишите доказательство?

[maxal]

Можно попробовать так:

$$S(a) = \sum_{k=1}^{p-1} \int_0^a x^{k-1}dx = \int_0^a dx \frac{x^{p-1}-1}{x-1}$$

Положим

$$I(f(x),L,U) := \int_L^U (x^{p-1}-1) f(x)\,dx$$

Тогда

$$I(f(x),L,U) \equiv I( 2f(2x), \frac{L}2, \frac{U}2)\pmod{p}$$

$$I(f(x),L,U) \equiv I( \frac{x}{x+1} f(x+1), L-1, U-1)\pmod{p}$$

$$I(f(x),L,U) \equiv I( \frac{x}{x-1} f(x-1), L+1, U+1)\pmod{p}$$

Осталось вычислить $I(\frac{1}{x-1},0,4) + I(\frac{1}{x-1},0,3) - 3I(\frac{1}{x-1},0,2)$.

[nnosipov]

maxal в сообщении #1406487 писал(а):

Осталось вычислить $I(\frac{1}{x-1},0,4) + I(\frac{1}{x-1},0,3) - 3I(\frac{1}{x-1},0,2)$.

Не вижу пока, как. Это делается?

А вообще, с интегралами мысль интересная. Мне тоже поначалу хотелось чего-то в этом духе (преобразование Абеля). Но потом я вспомнил одну старую задачу, и все прояснилось: ведь можно получить простую замкнутую формулу для $S(a) \bmod{p}$.

[wrest]

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

Ответ верный. Напишите доказательство?

Я на калькуляторе проверял

[nnosipov]

wrest в сообщении #1406501 писал(а):

Я на калькуляторе проверял

Тоже интересно: взять какое-нибудь 100-значное $p$ и проверить.

[wrest]

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

Тоже интересно: взять какое-нибудь 100-значное $p$ и проверить.

Проверил до $p=10007$

[alcoholist]

я что-то не понимаю... Если $p=3$, то число

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

$S(4)+S(3)-3S(2)$

равно $15/2$, то есть не является целым.

[nnosipov]

wrest в сообщении #1406506 писал(а):

Проверил до $p=10007$

Это понятно, что Вы проверили до некоторой разумной (для прямого счета) границы. Собственно, вот содержательный вопрос: как подсчитывать $S(a) \bmod{p}$ при больших $p$? В некотором смысле это даже интересней, чем решать исходную задачу.

alcoholist
Имеются в виду арифметические операции по модулю $p$ (сумму вычисляем не в $\mathbb{Q}$, а в $\mathbb{Z}_p$).

[maxal]

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

Не вижу пока, как. Это делается?

Я тоже теперь не вижу.

[nnosipov]

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

ведь можно получить простую замкнутую формулу для $S(a) \bmod{p}$.

На самом деле, и это вычисление тоже было представлено на форуме, правда в неявной форме: см. http://dxdy.ru/post892365.html#p892365

[maxal]

Ага, я чуть-чуть до этого не дошел, все пытался что-то подобное по модулю $p$ сделать, а тут оказывается надо играть на повышение:

$$pS(a) \equiv \sum_{k=1}^{p-1} (-1)^{k-1}\binom{p-1}{k-1} \frac{p}{k} a^k = \sum_{k=1}^{p-1} (-1)^{k-1} \binom{p}{k}a^k = a^p + (1-a)^p - 1\pmod{p^2}$$

Соответственно:

$$pS(4) + pS(3) - 3pS(2) \equiv (4^p - 3^p - 1) + (3^p - 2^p - 1) - 3(2^p - 2) \equiv 4^p - 4\cdot 2^p + 4 \equiv (2^p - 2)^2\equiv 0 \pmod{p^2}.$$

Красиво!

[nnosipov]

Да, мне тоже понравилось, поэтому и решил поделиться. Первоисточник: Problem Shortlist IMO 2011 Там есть еще одно решение, без явной формулы для $S(a)$.