Нужна подсказка/решение по данной задаче
Также до этого была получена подсказка, которую я не смог использовать,
Подсказка была следующей: Пусть f(a) функция такая что a^{p-1} \equiv 1 + pf(p) (mod p^2), тогда:
(p-1)^{p-1} = \prod_{a = 1}^{p-1}a^{p-1} \equiv \prod_{a=1}^{p-1}(1 + pf(a))\equiv 1 + \sum_{a=1}^{p-1}f(a)(modp^2)
По малой теореме Ферма выполняется сравнение
(ab)^{p-1} - 1 = b^{p-1}(a^{p-1} - 1) + b^{p-1} - 1\equiv (a^{p-1} - 1) + (b^{p-1} - 1) \pmod{p^2},
где (a, p) = (b, p) = 1.
Следовательно,
\sum_{k=1}^{p-1}(k^{p-1}-1)\equiv \prod_{k=1}^{p-1}k^{p-1}-1 = ((p-1)! + 1 - 1)^{p-1} - 1 \equiv \\
\equiv (p-1)((p-1)! + 1)(-1)^{p-2} \equiv (p-1)! + 1 \pmod{p^2},
откуда получаем требуемое сравнение.
7 лайков
а почему b^{p-1} \equiv 1 (modp^2)?
Это не совсем правда.
Здесь мы пользовались тем, что
b^{p-1}(a^{p-1} - 1) -(a^{p-1} -1) = (b^{p-1} - 1)(a^{p-1} - 1)
делится на p^2, так как каждая из двух скобок делится на p. Таким образом,
b^{p-1}(a^{p-1}-1) \equiv a^{p-1} - 1 \pmod{p^2}.
Однако это не означает, что b^{p-1} \equiv 1 \pmod{p^2}.
5 лайков
можно еще расписать как получается
((p-1)! + 1 - 1)^{p-1} - 1 \equiv (p-1)((p-1)! + 1)(-1)^{p-2}
1 лайк
Распишем это выражение по биному Ньютона:
((p-1)! + 1 - 1)^{p-1} = \sum_{k = 0}^{p-1}{{p-1}\choose k}((p-1)! + 1)^{k}(-1)^{p-1-k}.
По теореме Вильсона, ((p-1)! + 1)^k делится на p^2 при k \geq 2. Следовательно,
\sum_{k = 0}^{p-1}{{p-1}\choose k}((p-1)! + 1)^{k}(-1)^{p-1-k} \equiv (-1)^{p-1} + {{p-1}\choose 1}((p-1)! + 1)(-1)^{p-2} \equiv \\
\equiv 1 + (p-1)((p-1)! + 1)(-1)^{p-2} \pmod{p^2}.
5 лайков
Все понял, спасибо!