Решение

Мне в голову пришло два разных подхода. Первый крестьянский, второй несколько магический.

1) (Полиномиальное) Давайте подумаем, как вообще вычислять суммы вида x_1^k + x_2^k + ... + x_n^k для какого-то набора x_i и какого-то (достаточно большого) k. Есть стандартная идея, как делать это по индукции: рассмотрим полином P(x) = (x - x_1)(x - x_2) ... (x - x_n) = x^n + a_(n-1)x^(n-1) + ... + a_0. Ясно, что P(x_i) = 0, потому x_i^n = - a_(n-1)x_i^(n-1) - ... - a_0. Суммируя это тождество по всем i получим выражение суммы n степеней через суммы меньших степеней. Далее можно выражать суммы больших степеней по индукции, пользуясь аналогичным тождеством x_i^s * P(x_i) = 0, на каждом шаге нам нужно будет знать значения n меньших сумм. Давайте далее для удобства обозначать сумму k степеней как s_k.

В нашем случая полином P(x) = (x - 1)(x - 2) ... (x - (p - 1)). Заметим, что все его коэффициенты кроме старшего и младшего делятся на p, так как над F_p он равен полиному x^(p-1) - 1 по малой теореме Ферма. Также легко видеть, что s_1, s_2, ... s_(p-1) все делятся на p — понять это можно примерно как угодно, проще всего используя первообразный корень по модулю p. Теперь применяя описанную выше технику видим, что s_(p-1) = - a_(p-2) * s_(p-2) - ... - a_1 * s_1 - a_0 * (p - 1), и, к нашему великому счастью, все слагаемые кроме a_0 * (p - 1) делятся на p^2, откуда s_(p-1) сравнимо с - (p - 1)!(p - 1) ~ - p * (p - 1)! + (p - 1)! ~ p + (p - 1)!

2) (p-адическое) Второй подход несколько более мистический, хотя не требует даже знаний многочленов над F_p. Ясно, что вычисления по модулю p легче, чем по модулю p^2, потому попробуем свести все к ним, держа в голове, что всякий остаток mod p^2 можно мыслить как a + b*p, где a и b это остатки по модулю p. Заметим, что x^(p-1) - 1 кратно p по МТФ при x не делящимся на p, потому положим x^(p - 1) = 1 + k_x * p и так как нас все интересует по модулю p^2 можно мыслить k_x просто как вычет по модулю p. Аналогично пусть (p - 1)! = - 1 + t * p.

Далее 1^(p-1) + 2^(p-1) + ... ~ (p - 1) + (sum k_i) * p потому нам нужно придумать, как связать sum k_i с t по модулю p (а не p^2 !). И тут кроется главная нетривиальная идея этого решения: давайте посмотрим на выражение (p - 1)! ^ (p - 1). С одной стороны оно равно prod (1 + pk_x) ~ 1 + p * sum k_x (mod p^2) а с другой оно же равно ( - 1 + t*p)^(p - 1) ~ 1 - (p - 1)*t*p ~ 1 + p*t, что дает нам искомую связь t и (sum k_i) по модулю p.

3) ? Наверное, эту задачу также можно решить, используя технику когомологий этальных пучков, но я пока так не умею, возможно, допишу пост, как научусь.