On the congruence ${1^n + 2^n + \dotsb + n^n\equiv p \pmod{n}}$

Max Alekseyev, Jose Maria Grau, Amtonio Oller-Marcen

Published 2016-02-07Version 1

It is well-known that the congruence $\sum_{i=1}^{n} i^{n} \equiv 1 \pmod{n}$ has exactly five solutions: $\{1,2,6,42,1806\}$. In this work, we characterize the solutions to the congruence in the title for every prime $p $. This characterization leads to an algorithm that allows to compute all such solutions when there is finite number of them and, in general, to find all the solutions up to very high bounds in comparison to the computational complexity appearing if the problem is naively addressed by exhaustive search.