Computing solutions to the congruence $1^n+2^n+\cdots +n^n\equiv p(\mathrm{mod}n)$

Abstract

It is well-known that the congruence ${\sum }_{i=1}^n{i}^n\equiv 1(\mathrm{mod}n)$ has exactly five solutions: $\{1,2,6,42,1806\}$. In this work, we characterize the solutions to the congruence $1^n+2^n+\cdots +n^n\equiv p(\mathrm{mod}n)$ for every prime $p$. This characterization leads to an algorithm for computing all such solutions, when there is a finite number of them. More generally, our algorithm enables computing all the solutions below a much higher bound as compared to what can be achieved by a naive exhaustive search.

References in corpus (2)

• Power-Sum Denominators
• On the congruence $1^m+2^m+\cdots +m^m\equiv n(\mathrm{mod}m)$ with $n|m$