Post History

## Assumed question
### Placement of parentheses
Your final paragraph suggests that you would already know how to evaluate the following expression:

$$ \Bigl( \sum_{i=1}^{N} (a \cdot i) \Bigr) \bmod{M} $$

I will therefore assume that your question concerns the following expression:

$$ \sum_{i=1}^{N} \Bigl( (a \cdot i) \bmod{M} \Bigr) $$

### Restriction to natural numbers
I will also assume that you are only interested in the cases where all of $N$, $a$, and $M$ are positive integers.

## Hints towards a solution
You may find it easier to reach a solution by breaking this problem down into 2 cases.

### Case 1: $a$ and $M$ are coprime
Here every contiguous set of $M$ terms will contain every non-negative integer less than $M$. This means that when $N$ is a multiple of $M$, the sum will be that same multiple $\frac{N}{M}$ of the sum of the first $M-1$ positive integers. Since the sum of the first $n$ positive integers is $\frac{n}{2}(n+1)$, the sum of the first $M-1$ positive integers (equivalently, the sum of the first $M$ non-negative integers) is $\frac{M(M-1)}{2}$.

When $N$ is not a multiple of $M$, there will be an additional $N\bmod{M}$ terms to add onto that sum. Note that these $N\bmod{M}$ terms will be identical to the first $N\bmod{M}$ terms, so the problem reduces to finding:

$$ \sum_{i=1}^{N \bmod{M}} \Bigl( (a \cdot i) \bmod{M} \Bigr) $$

So the final solution will be the sum of the identical repetitions, plus any left over terms:

$$ \left\lfloor\frac{N}{M}\right\rfloor \frac{M(M-1)}{2} + \sum_{i=1}^{N \bmod{M}} \Bigl( (a \cdot i) \bmod{M} \Bigr) $$

### Case 2: $a$ and $M$ are not coprime
In this more general case, instead of repeating every $M$ terms, there will be repetition every $\frac{M}{\gcd(a,M)}$ terms.

When $N$ is a multiple of $\frac{M}{\gcd(a,M)}$ the sum will be that multiple $\frac{N\gcd(a,M)}{M}$ of the sum of the first $\frac{M}{\gcd(a,M)}$ terms.

When $N$ is not a multiple of $\frac{M}{\gcd(a,M)}$ there will be an additional $N \bmod{\frac{M}{\gcd(a,M)}}$ terms to add onto that sum. Note that these terms will be identical to the first $N \bmod{\frac{M}{\gcd(a,M)}}$ terms, so the problem reduces to finding:

$$ \sum_{i=1}^{N \bmod{\frac{M}{\gcd(a,M)}}} \Bigl( (a \cdot i) \bmod{M} \Bigr) $$

So the final solution will be the sum of the identical repetitions, plus any left over terms:

$$ \left\lfloor\frac{N\gcd(a,M)}{M}\right\rfloor \sum_{i=1}^{\frac{M}{\gcd(a,M)}} \Bigl( (a \cdot i) \bmod{M} \Bigr) + \sum_{i=1}^{N \bmod{\frac{M}{\gcd(a,M)}}} \Bigl( (a \cdot i) \bmod{M} \Bigr) $$

This does not give you a closed form solution, but it does give you something that in some cases will give a far faster solution by looping, and may also hint at potential further improvements.