Timeline for Is there a way to find the value of $1^n+ 2^n +\cdots + m^n$ modulo $x$?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2012 at 18:25 | comment | added | Thomas Andrews | Sorry, that only works when both $x$ and $n$ are odd. If $x$ is even and $n$ odd, then $1^n+2^n+..+x^n\equiv (\frac{x}{2})^n \pmod x$. If $x$ is divisible by $4$ and $n>1$, then $(\frac x 2)^n \equiv 0\pmod x$. | |
| Nov 17, 2012 at 18:19 | comment | added | Thomas Andrews | One quick reduction occurs when $n$ is odd. Then the expression $1^n+2^n+...+x^n \equiv 0\pmod x$. That's because $a^n + (x-a)^n \equiv 0\pmod x$. | |
| Nov 17, 2012 at 18:18 | history | edited | sperners lemma | CC BY-SA 3.0 |
added 40 characters in body
|
| Nov 17, 2012 at 18:17 | comment | added | sperners lemma | @ThomasAndrews, so we need a,x coprime. Thanks very much for pointing this out. | |
| Nov 17, 2012 at 18:14 | comment | added | Thomas Andrews | Yeah, I got the formula wrong in my comment above, but my counter-example is for your second version. There, $a=2$, $x=8$, $n=1$ and $n'=5$. | |
| Nov 17, 2012 at 18:13 | comment | added | sperners lemma | @ThomasAndrews, In the first part I'm using $n \equiv n' \pmod{\varphi(x)}$ then $a^n \equiv a^{n'} \pmod {x}$. I think holds in all cases. In the second part I'm just using $a \equiv b \pmod x$ then $a^n \equiv b^n \pmod x$. | |
| Nov 17, 2012 at 18:13 | comment | added | Thomas Andrews | If $x=8$ then $\varphi(x)=4$ and $2^5\equiv 0 \not\equiv 2^1\pmod 8$ even though $5\equiv 1\pmod 4$ | |
| Nov 17, 2012 at 18:10 | comment | added | Thomas Andrews | $\varphi(x)$ doesn't do you any good, because the numbers from $1$ to $x$ are not all relatively prime to $x$. In general, it is not true that if $a\equiv b\pmod {\varphi(x)}$ that $a^{\varphi(x)}\equiv b^{\varphi(x)}\pmod x$ | |
| Nov 17, 2012 at 16:20 | vote | accept | abhishek srivastava | ||
| Nov 17, 2012 at 15:00 | history | answered | sperners lemma | CC BY-SA 3.0 |