10
$\begingroup$

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

  • 0
    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.2010-08-29
  • 0
    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 :\2010-08-29
  • 0
    The next entry is 1806. Does it work?2010-08-29
  • 1
    3263442 is wrong, the result of modding is 1807. Similarly, 47058 -> 5797, 3270666 -> 1811.2010-08-29
  • 0
    The next smallest m satisfying the condition is 1806, which coincides with A007018. But as KennyTM commented, 3263442 does not satisfy the condition.2010-08-29
  • 1
    Probably it is [A014117](http://www.research.att.com/~njas/sequences/A014117)?2010-08-29
  • 0
    @Eugene: Probably you should put the EDIT 2 as answer. (Although I don't see A014117 is a proof that there are at most 4 numbers in your case.)2010-08-29
  • 0
    Done so below. Should I accept it as well?2010-08-29
  • 0
    @Eugene: If you think it completely solves the problem, yes. (Although you can't accept it within 24 hours).2010-08-29
  • 0
    As of yet I'm stuck on relating it to the original problem...2010-08-29
  • 0
    You claim that the correct sequence is A014117, and you write that you do not know why. Something is wrong there.2010-08-29
  • 0
    After running through thousands of numbers those were the only ones that worked... while that's not a proof in itself, the pattern is the same and I'm sure there is some sort of relation. I have not yet found it. If you would like to help _find_ that relation, that would be much more helpful than simply saying I'm wrong and doing nothing about it.2010-08-29
  • 0
    Well, n^m mod m takes on a limited amount of numbers on the range [1,m]. For example, for m = 42, all n^m mod m are members of {0,1,7,15,21,22,28,36}. 0 only occurs when n = m, 21 only occurs when n = 21 = m/2. 1 and 22 occur 12 times, which is the same as phi(n) (total of numbers coprime to m less than m, a.k.a. Euler Totient Function). This is interesting because it also applies to m = 1806! of all the values the mod takes on, it takes on 903 (1806/2) exactly once, and takes on 1 and 904 exactly 504 times, which is phi(1806). Then what do the other numbers mean?2010-08-29
  • 0
    To clarify, n^m mod m takes on only as many values as there are divisors of m. For each unique value of gcd(n,m), n^m mod m takes on exactly one value. For example: if gcd(n,m) = 2 (e.g. 2, 4, 8), then n^m mod m = 22 if gcd(n,m) = 7 (e.g. 7, 35), then n^m mod m = 7 etc.2010-08-29
  • 0
    The current wording of the question states a conjecture as if it were a known fact, which makes it difficult to understand the current situation. I have been trying to help you improve the wording of the question. Of course, I would like to help you in another direction, namely prove your conjecture, but the problem is difficult for me and I have not succeeded. You can keep accusing me of not doing anything useful if you would like to.2010-08-29
  • 0
    I modified it to be a little more clear... is this better? I added some information that may be more relevant.2010-08-29
  • 0
    I have an unfinished proof developing here: http://mathbin.net/51297 anything I missed? I feel like I'm almost there...2010-08-29

1 Answers 1

2

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

  • 0
    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?2010-08-31
  • 0
    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$.2010-08-31
  • 0
    @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?2010-09-02
  • 0
    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.2010-09-02
  • 0
    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}$.2010-09-02
  • 0
    The mathoverflow answer is correct. The claim there is that, if m is such that for every prime p which divides m, p^2 does not divide m and p-1 divides m, then m is one of the finite set you have. What you seem to state here (that n^(m+1) = n mod p implies n^(m+1) = n mod m) is completely different and I am not sure it is correct. Also, please give credit to the person who came up with that. From your answer it sounds like you have come up with it yourself.2010-09-03
  • 0
    If I have misread, I do apologize.2010-09-03
  • 0
    in the first line I said I made a proof out of it, but I also immediately link to where each part was solved. I'm not taking responsibility for the solution, just the format. the thing is that the problem was originally a question asking to find the sum of all integers such that the sum was equivalent to 1 mod m, so I had to reformat the proof.. that may have led to some incorrect statements. if that is the case I'll correct it, but right now I can't see how to correct it :\2010-09-05