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$?

Question

It can be seen here 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, 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?

Answer 1

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.

Answer 2

We have, for both congruences, if $p$ is a prime dividing $m$, then $p-1$ also divides $m$, and $p^2$ doesn't divide $m$; conversely, if $m$ satisfies these properties, then it works in both congruences. No Bernoulli numbers are necessary.

Let $p$ be a prime dividing $m$. Then $\sum_{n=1}^mn^m\equiv1\bmod p$, so $(m/p)\sum_{n=1}^{p-1}n^m\equiv1\bmod p$, so $p^2$ doesn't divide $m$. Let $g$ be a primitive root mod $p$. Then $\sum_{n=1}^{p-1}n^m\equiv\sum_{r=0}^{p-2}g^{rm}$. That's a geometric series, it sums to $(1-g^{(p-1)m})/(1-g^m)$ which is zero mod $p$ - unless $g^m=1$, in which case it sums to $-1$ mod $p$. So we must have $p-1$ dividing $m$.

Now look at the other congruence, $n^{m+1}\equiv n\bmod m$. Letting $n=p$, we see that $p^2$ can't divide $m$. Now looking mod $p$, we get $n^{m+1}\equiv n\bmod p$. This is equivalent to $m+1\equiv1\bmod{p-1}$, that is, $p-1$ divides $m$.

It's not hard to show that the only $m$ such that for every prime $p$ dividing $m$ we have $p-1$ divides $m$ and $p^2$ doesn't divide $m$ are those numbers 1, 2, 6, 42, and 1806. First show that if any prime divides $m$ then 2 divides $m$. The if more than one prime divides $m$ show that the second smallest must be 3. Then if more than 2 primes divide $m$ the third smallest must be 7. And so on.

Answer 3

I don't see how to find all $m$ for which $\sum_{k=1}^m k^m \equiv 1 \bmod{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\bmod{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 \bmod{ m }$ for all $a$, then $\sum_{k=1}^m k^m \equiv 1 \bmod{m}$.

To prove this first we make the observation that if $a^{m+1}\equiv a \bmod{m}$ for all $a$ then $\sum_{k=1}^m k^m \equiv \sum_{d|m}\phi(\frac{m}{d})d^m = F(m) \bmod{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\bmod{m}.$$ By considering the expression modulo each prime separately this breaks down to the congruences $m/p_i\equiv -1\bmod{p_i}$ which are satisfied by all $m$ which we were considering.

Answer 4

we can write: $\displaystyle\int_{0}^{m}{x^m}dx\le\sum_{n=1}^{m}{n^m} \le\int_{0}^{m+1}{x^m}dx$

so $\displaystyle\frac{m^{m+1}-(m+1)-m(m+1)k}{m+1}\le\sum_{n=1}^{m}{n^m}-1-mk-\le\frac{(m+1)^{m+1}-(m+1)-m(m+1)k}{m+1}$ and then $\displaystyle\frac{m^{m+1}-(m+1)-m(m+1)k_1}{m+1}\le\sum_{n=1}^{m}{n^m}-1-mk-\le\frac{(m+1)^{m+1}-(m+1)-m(m+1)k_2}{m+1}$ in which assume that $k_2\le k$ and$k\le k_1$,

but since $(m+1)^{m+1}\equiv{m+1}\pmod{m}$ and also $m^{m+1}\equiv m\pmod{m}$ so the

central statement should be zero, or $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1\bmod m$, when the first

congruence holds for the numbers 1,2,6,42,1806, second one holds for these numbers.

note: if $m$ be an even number so $m^{m}-1$ is divided to $m+1$ then $(m+1)^{m+1}\equiv{m+1}\pmod{m(m+1)}$ and $m^{m+1}\equiv m\pmod{m(m+1)}$ the above inequalities is hold for some $m$