# Is there a way to find the value of $1^n+ 2^n +\cdots + m^n$ modulo $x$?

I am writing a program in which I want to make changes to make it more efficient.

What the program does is it takes three inputs $m$, $n$ and $x$ and I have to find the value of the following equation: $$1^n+ 2^n+\cdots + m^n \mod{x}$$

Is there a better way than calculating the whole value and then solving for answer? Because if $n$ and $m$ are large it takes a lot of computation time which I am trying to avoid.

-

1
What about wikipedia:bernoulli-polynomials , or googling for "sums-of-like-powers" ? – Gottfried Helms Nov 17 '12 at 14:36
please note I made a mistake in my answer. – sperners lemma Nov 17 '12 at 18:20

## 1 Answer

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

• Edit: This is wrong, don't do this: Replace $n$ with its remainder on division by $\varphi(x)$. this only works for the bases coprime to n, which is a good proportion so it may still be worth it to do that.. for ones that aren't coprime...

• Use binary exponentiation.

• Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).

-

1
$\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$ – Thomas Andrews Nov 17 '12 at 18:10

1
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$ – Thomas Andrews Nov 17 '12 at 18:13

1
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$. – Thomas Andrews Nov 17 '12 at 18:14

1
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$. – Thomas Andrews Nov 17 '12 at 18:19

1
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$. – Thomas Andrews Nov 17 '12 at 18:25
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 43, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9335286021232605, "perplexity_flag": "head"}