2

How to calculate $$\frac{n^2(n + 1)}2 \bmod m$$ where $1 \leq n \leq 10^{16}$ and $1 \leq m \leq 10^7$?

Here $m$ and $n$ are integers.

What I have done:

if n is even: $$\frac{n^2(n + 1)}2 \bmod m = {(\frac{n}{2} \bmod m)(n\bmod m)((n + 1) \bmod m)} \bmod m$$ if n is odd $$\frac{n^2(n + 1)}2 \bmod m = {(n \bmod m)(n\bmod m)(\frac{n+1}{2} \bmod m)} \bmod m$$

I am having difficulty in continuing.

Jyrki Lahtonen
  • 133,153
Sud
  • 21
  • 2
    Check your way of writing mathematics here and make clear your intention. It'd be fine to know what've you attempted so far to solve your problem as well.http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-qu%E2%80%8C%E2%80%8Bick-reference – Timbuc Feb 07 '15 at 12:08
  • What is the "%m"? – user103828 Feb 07 '15 at 12:14
  • m is an integer – Sud Feb 07 '15 at 12:25
  • This has nothing whatsoever to do with either integer programming or division algebras. This should be plain to anyone who bothered to look at the tag excerpt (the text that shows when you mouseover a tag). Tsk. Tsk :-( – Jyrki Lahtonen Feb 17 '15 at 22:34

1 Answers1

0

Assuming here $\%$ means mod

The tricky part of this question is the $\frac12$ inside the equation. To get rid of that I solve this remainder question for odd and even $n$ separately.

Also, we suppose that

$$n=qm+r$$

where r is the remainder.

and

$$A=\frac12n^2(n+1)$$

$$A \% m = ?$$

(I) if n is even:

$$n=2k$$

$$A=\frac12n^2(n+1)=2k^2(2k+1)=2k^2(qm+r)$$

$$A\%m=2 r(\frac12n\%m)^2 \%m$$

Which is much simpler in computation.

(II) if n is odd: $$n=2k+1$$ $$A=\frac12n^2(n+1)=(2k+1)^2(k+1)$$

$$A\%m= r^2(\frac12(n+1)\%m) \%m$$

Again much simpler than original question.

Arashium
  • 2,541