# Why are the only numbers $m$ for which $n^{m+1}\equiv n \pmod{m}$ also the only numbers such that $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1 \bmod m$?

It can be seen here that the only numbers for which $n^{m+1}\equiv n \pmod{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 \pmod{\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} \pmod 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?

-
thank you, Qiaochu. hopefully there will be a little more activity here... –  DoubleAW Aug 29 '10 at 23:49

Let $m > 2$ be an integer such that $S_m(m) = \sum_{n=1}^{m-1} n^m\equiv 1 \pmod{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\pmod{m}$. It is now clear that $m$ must be square -free as otherwise $S_m(m) \not\equiv 1\pmod{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.

-
That's neat! Your answer combined with my observation gives the bijection between the two solution sets without having to check anything by hand or even explicitly writing down the solutions. –  Gjergji Zaimi Aug 30 '10 at 11:01
VERY cool. Is this the simplest way to solve it? Or are there ways that don't require Bernoulli numbers? –  DoubleAW Aug 30 '10 at 11:40
Maybe it helps to write $\binom m k \frac 1 {k+1}$ as $\binom {m+1}{k+1} \frac 1 {m+1}$. It's then also clear that only one term remains, without distinguishing cases. (In fact, there's a factor of $m$ missing in your second term.) When you wrote "$p$-integral" you meant "prime to $p$". Anyway, very nice. –  fherzig Aug 30 '10 at 14:45

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\pmod p$, so $(m/p)\sum_{n=1}^{p-1}n^m\equiv1\pmod 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\pmod m$. Letting $n=p$, we see that $p^2$ can't divide $m$. Now looking mod $p$, we get $n^{m+1}\equiv n\pmod p$. This is equivalent to $m+1\equiv1\pmod{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.

-
I was about to comment that there was no need for Bernoulli numbers, since one can redo the start of the proof of Clausen and von Staudt by hand. And that is exactly what you have outlined here. Since the question was about congruence of $S_m(m)$ modulo $m$ I thought the "$m$-adic development" of it might have some additional interest. –  Chris Wuthrich Aug 30 '10 at 13:39
While I accepted the first answer (Chris's), I do like this one because of its simplicity and, as Chris stated, its lack of Bernoulli numbers and whatever. Thank you! –  DoubleAW Aug 30 '10 at 20:54
One quick thing: why is $n^{m+1}\equiv n\pmod p$ equivalent to $m+1\equiv1\pmod{p-1}$? –  DoubleAW Aug 30 '10 at 21:11
@DoubleAW, it follows from $n^p\equiv n\pmod p$ and $n^{p-1}\equiv1\pmod p$. Write $m+1=(p-1)q+r$ with $2\le r\le p$ and plug it in. –  Gerry Myerson Aug 30 '10 at 22:44
I just looked up Euler's theorem on Wikipedia and it was right there, yeah. If $a^x \equiv a^y \bmod{n}$, then $x \equiv y \bmod{\phi(n)}$, and $\phi(p) = p-1$. –  DoubleAW Aug 30 '10 at 22:55

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.

-

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$

-
I've attempted to clean up the TeX, but remain baffled by the math. –  Gerry Myerson Sep 1 '10 at 2:53
which part of above answer is not clear? –  M.S Sep 1 '10 at 18:24
almost all of it. Can you expand ? –  Chris Wuthrich Sep 1 '10 at 23:24