Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
3263442 is wrong, the result of modding is 1807. Similarly, 47058 -> 5797, 3270666 -> 1811. –  KennyTM Aug 29 '10 at 7:28
1  
Probably it is A014117? –  KennyTM Aug 29 '10 at 11:59

1 Answer 1

up vote 2 down vote accepted

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\}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.