# Why are the only numbers $m$ for which $n^{m+1}\equiv n \pmod{m}$ is true also unique for $\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}$?

-
Have you checked to see if the other entries of A007018 work? (Also, the second paragraph doesn't mean much; you are just subtracting 1 from both sides and using the fact that m^m is divisible by m. –  Qiaochu Yuan Aug 29 '10 at 2:21
yeah, I only noted it due to the whole odd numbers lead to getting 0 when taken mod m. and the next entry is 3263442... I don't think I have the computational power to check it :\ –  Eugene Bulkin Aug 29 '10 at 4:38
The next entry is 1806. Does it work? –  Qiaochu Yuan Aug 29 '10 at 6:02
3263442 is wrong, the result of modding is 1807. Similarly, 47058 -> 5797, 3270666 -> 1811. –  kennytm Aug 29 '10 at 7:28
Probably it is A014117? –  kennytm Aug 29 '10 at 11:59

Well, I've made a full proof! Part 1 was solved here, and Part 2 was solved here.

Lemma 1: Any integer $m$ which satisfies the original problem also satisfies $n^{m+1} \equiv n \bmod{m}$ for all $n$.

Proof: 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$. Looking at $n^{m+1}\equiv n\pmod m$ and letting $n=p$, we see that $p^2$ cannot 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}$ (if $a^x \equiv a^y \bmod{n}$, then $x \equiv y \bmod{\varphi(n)}$ by Euler's theorem, and $\varphi(p) = p-1$), that is, $p-1$ divides $m$, so any integer $n^{m+1} \equiv n \bmod{m}$ as $p-1|m$ for all $m$ if $p|m$.

Lemma 2: There are only a finite amount of integers $m$ which satisfy $n^{m+1} \equiv n \bmod{m}$

Proof: Since $p^2$ does not divide $m$, we may let $m = p_1 \ldots p_r$ with $p_1 < p_2 < \ldots < p_r$, with $p_i$ prime; as $p-1|m$ for all $p|m$, we say that $p_i-1|p_1 \ldots p_{i-1}$ for $i = 1, \ldots, r$. If we take $i = 1$, this forces $p_1-1|1$, so if $r \ge 1$, $p_1 = 2$. If $i = 2$, $p_2-1|2$, so if $r \ge 2$, $p_2 = 3$. Continuing, if $r \ge 3$, then $(p_3-1)|p_1 p_2 = 6$, so $p_3 = 7$; if $r \ge 4$, $(p_4 - 1)|p_1 p_2 p_3 = 42$, so $p_4 = 43$, as the numbers $d+1$ are not prime for other divisors $d$ of 42 larger than 6. If $r \ge 5$, then $(p_5 -1)|p_1 p_2 p_3 p_4 = 1806$, but 1, 2, 6 and 42 are the only divisors of 1806 with $d+1$ prime, so $p_5$ cannot exist. Therefore, $r \le 4$ and $m \in \{1, 2, 6, 42, 1806\}$.

-
I don't see how $n^{m+1} = n \mod m$ follows from $n^{m+1} = n \mod p$. Aren't those theorems etc useful only if $n$ and $m$ (or $p$) are co-prime? Care to explain a bit more? –  Aryabhata Aug 31 '10 at 14:46
If $p$ divides $m$, then two things will be the same $\bmod{m}$ and $\bmod{p}$, I believe. And they work regardless of whether $n$ and $m$ are coprime, especially because $n$ is just a number from 1 to $m$. –  Eugene Bulkin Aug 31 '10 at 22:18
@Eugene: Those theorem are not guaranteed to work if we remove the co-prime condition. Not sure why you think so. Do you have a reference? –  Aryabhata Sep 2 '10 at 3:25
the only reference I really have is the link I added to the proof on mathoverflow. there is a more reliable proof (with bernoulli numbers) but that's a little too advanced, so I prefer this one. –  Eugene Bulkin Sep 2 '10 at 15:39
As for the theorems: Let $a$, $b$, and $n$ be integers, and let $p$ be a prime dividing $n$. If $a \equiv b \bmod{n}$, then $a = b+j n$ where $j$ is any integer. Because $p|n$, $n = k p$ for some integer $k$, meaning $a = b + j k p$. Since $j k p$ is an integer multiple of $p$, it can be said that $a \equiv b \bmod{p}$. –  Eugene Bulkin Sep 2 '10 at 22:20