Timeline for Why are the only numbers $m$ for which $n^{m+1}\equiv n \bmod m$ also the only numbers such that $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1 \bmod m$?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2016 at 5:26 | history | edited | Włodzimierz Holsztyński | CC BY-SA 3.0 |
"\bmod" instead of "\pmod"
|
| Sep 3, 2010 at 10:32 | comment | added | Gerry Myerson | If $p$ is prime then there exists $g$, called a primitive root, such that the integers $1,2,\dots,p-1$ are congruent to $g^0,g^1,\dots,g^{p-2}$ (mod $p$), in some order. The sum is zero because $g^{p-1}\equiv1\pmod p$. I'd recommend you read some intro Number Theory text if you're interested in this sort of thing - that's not what MO is for. | |
| Sep 2, 2010 at 22:31 | comment | added | DoubleAW | Yes, that's what I meant. I didn't say that was Euler's theorem. It's just a result. @Gerry, could you explain the logic of the primitive root business? I'm not too knowledgeable about them and so I'm unsure as to why you can make that equality (the $n^m$ = $g^{rm}$ one, that is), and why the sum is zero $\bmod{p}$. | |
| Sep 1, 2010 at 13:53 | comment | added | Gerry Myerson | @JBL, maybe DoubleAW has just left out a quantifier. If $a^x\equiv a^y\pmod n$ for all $a$, then $x\equiv y\pmod{\phi(n)}$. | |
| Sep 1, 2010 at 11:57 | comment | added | JBL | That's not a correct statement of Euler's theorem -- you've got the implication going the wrong way. (E.g., $3^3 \equiv 3^0 \pmod{13}$ but obviously 3 is not divisible by 12.) | |
| Aug 30, 2010 at 22:55 | comment | added | DoubleAW | 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$. | |
| Aug 30, 2010 at 22:44 | comment | added | Gerry Myerson | @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. | |
| Aug 30, 2010 at 21:11 | comment | added | DoubleAW | One quick thing: why is $n^{m+1}\equiv n\pmod p$ equivalent to $m+1\equiv1\pmod{p-1}$? | |
| Aug 30, 2010 at 20:54 | comment | added | DoubleAW | 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! | |
| Aug 30, 2010 at 13:39 | comment | added | Chris Wuthrich | 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. | |
| Aug 30, 2010 at 13:11 | history | answered | Gerry Myerson | CC BY-SA 2.5 |