3
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ thank you, Qiaochu. hopefully there will be a little more activity here... $\endgroup$
    – DoubleAW
    Aug 29, 2010 at 23:49
  • $\begingroup$ $\LaTeX$ seem to play up, thus let me test mod, bmod, pmod, pod. *** $a\equiv v \mod{\theta}$ *** $a\bmod b$ *** $a\equiv v \pmod{\theta}$ *** $a\eqiv v\pod{\theta}$. *** This drives me crazy!!! $\endgroup$ Jan 2, 2016 at 5:54
  • $\begingroup$ Only \bmod seems to work (of the four operations above). $\endgroup$ Jan 2, 2016 at 5:57
  • 1
    $\begingroup$ @WłodzimierzHolsztyński Whatever the issue with pmod might be, it's worth confirming whether it is localized and/or temporary before making wholesale edits such as these. $\endgroup$ Jan 2, 2016 at 11:28
  • 1
    $\begingroup$ @Włod, they push this old question onto the front page – thereby pushing some newer question off the front page – for what may turn out to be no good reason. Also, they may run counter to the wishes of those whose posts are being edited. $\endgroup$ Jan 2, 2016 at 15:28

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Aug 30, 2010 at 11:01
  • $\begingroup$ VERY cool. Is this the simplest way to solve it? Or are there ways that don't require Bernoulli numbers? $\endgroup$
    – DoubleAW
    Aug 30, 2010 at 11:40
  • $\begingroup$ 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. $\endgroup$
    – fherzig
    Aug 30, 2010 at 14:45
  • 2
    $\begingroup$ MO is not displaying $\LaTeX$ "\binom" nor \choose". Is it just me? $\endgroup$ Jan 2, 2016 at 5:39
7
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Aug 30, 2010 at 13:39
  • $\begingroup$ 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! $\endgroup$
    – DoubleAW
    Aug 30, 2010 at 20:54
  • $\begingroup$ One quick thing: why is $n^{m+1}\equiv n\pmod p$ equivalent to $m+1\equiv1\pmod{p-1}$? $\endgroup$
    – DoubleAW
    Aug 30, 2010 at 21:11
  • $\begingroup$ @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. $\endgroup$ Aug 30, 2010 at 22:44
  • $\begingroup$ 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$. $\endgroup$
    – DoubleAW
    Aug 30, 2010 at 22:55
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ MO is not displaying "\pmod". I replaced them with "\bmod". Is it only today? Is it my problem only? $\endgroup$ Jan 2, 2016 at 5:44
  • $\begingroup$ (at the moment) \pmod is nicely been displayed at my system (Win 7, Firefox) $\endgroup$ Jan 2, 2016 at 12:21
0
$\begingroup$

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$

$\endgroup$
3
  • 3
    $\begingroup$ I've attempted to clean up the TeX, but remain baffled by the math. $\endgroup$ Sep 1, 2010 at 2:53
  • $\begingroup$ which part of above answer is not clear? $\endgroup$
    – M.S
    Sep 1, 2010 at 18:24
  • $\begingroup$ almost all of it. Can you expand ? $\endgroup$ Sep 1, 2010 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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