It can be seen [here](http://www-groups.dcs.st-and.ac.uk/~john/Zagier/Solution1.1.html) that the only numbers for which $n^{m+1}\equiv n \bmod m$ is true are 1, 2, 6, 42, and 1806. Through experimentation, it has been found that $\displaystyle\sum\_{n=1}^{m}{n^m}\equiv 1 \bmod m$ is true for those numbers, and (as yet unproven) no others. Why is this true?


If there is a simple relation between $n^{m+1} \bmod{m}$ and $n^m \bmod{m}$, that would probably make this problem make more sense. It is obvious that $n^m \equiv 1 \bmod{\frac{m}{d}}$ (dividing out $n$ from both sides gives this result) for all $n$ on the interval $[1,m]$ where $d$ is a divisor of $m$. As a result of this, $n^m \bmod{m}$ takes on only values of the form $1+k \frac{m}{d} \bmod m$ where $k = -1, 0, 1$. How can it be shown that the sum of those values is equivalent to $1 \bmod{m}$?


I have a proof somewhat in the works [here](http://mathbin.net/51297), but it's not anywhere near complete (it doesn't even relate the 5 integers to the actual problem). Am I missing something in going from the first relation to the second?



Why are the only numbers $m$ for which $n^{m+1}\equiv n \bmod m$ also the only numbers such that $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1 \bmod m$?
Let $m > 2$ be an integer such that $S\_m(m) = \sum\_{n=1}^{m-1} n^m\equiv 1 \bmod{m}$. (Taking away $m^m$ does not harm the question, of course). Then $S\_m(m)$ has the following expression in terms of Bernoulli numbers:
\begin{equation\*}
S\_m(m) = \sum\_{k=0}^{m}\binom{m}{k}B\_{m-k}\frac{m^{k+1}}{k+1}
 = B\_m \cdot m + B\_{m-1} \frac{m^2}{2} + \binom{m}{2} B\_{m-2} \frac{m^3}{3} + \cdots
\end{equation\*}
By the theorem of Clausen and von Staudt, the denominator of $B\_k$ is the product of all primes $p$ such that $p-1$ divides $k$. In particular, they are square-free and hence we have the last displayed term and all that follow are conruent to $0$ modulo $m$. If the term
$B\_{m-1} \frac{m^2}{2}$ were not congruent to $0$ by the same argument, then $m$ would be even. But then $B\_{m-1}=0$ unless $m=2$.


So $S\_m(m) \equiv B\_m \cdot m\bmod{m}$. It is now clear that $m$ must be square -free as otherwise $S\_m(m) \not\equiv 1\bmod{m}$. Let $p$ be a prime dividing $m$. If now $B\_m\cdot m$ is $p$-integral, then $p-1$ must divide $m$. Now look at the answer to the question about the "wrong little Fermat". One derives that $m$ has to be in the list $\{1,2,6,42,1806\}$ just as before. Then one checks by hand that it is true for these integers.


