Skip to main content
1 of 2
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

I don't see how to find all $m$ for which $\sum_{k=1}^m k^m \equiv 1 \pmod{m}$, which seems to be difficult, but you ask only why do 1, 2, 6, 42, and 1806 work. One answer is that if you plug them in the expression you get $1\pmod{m}$ after a few computations, however this is not very illuminating so let me prove it once it is phrased like:

If $a^{m+1}\equiv a \pmod{ m }$ for all $a$, then $\sum_{k=1}^m k^m \equiv 1 \pmod{m}$.

To prove this first we make the observation that if $a^{m+1}\equiv a \pmod{m}$ for all $a$ then $\sum_{k=1}^m k^m \equiv \sum_{d|m}\phi(\frac{m}{d})d^m = F(m) \pmod{m}$. $F(m)$ is a multiplicative function and since $p^{\alpha-1}|F(p^{\alpha})$ then $m$ must be square free. Next we observe that if $m=p_1\cdots p_k$ then $$F(m)=\prod (p_i^m+p_i-1)$$ so we are left with proving $$\prod (p_i^m+p_i-1)\equiv 1\pmod{m}.$$ By considering the expression modulo each prime separately this breaks down to the congruences $m/p_i\equiv -1\pmod{p_i}$ which are satisfied by all $m$ which we were considering.

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402