Задача по теории чисел

Нужна подсказка/решение по данной задаче
image
Также до этого была получена подсказка, которую я не смог использовать,
Подсказка была следующей: Пусть 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},

откуда получаем требуемое сравнение.

6 симпатий

а почему 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 симпатий

Все понял, спасибо!

© 2021-2022 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)