Given: Two co-prime natural nos $a,b$
Find: $$S=\sum_{i=1}^n\left((ib)\bmod{a}\right)$$
i.e $$S=(b\bmod{a})+(2b\bmod{a})+(3b\bmod{a})+...+(nb\bmod{a})$$
My approach:
This is periodic with length of $a$.
If $n$ is a multiple of $a$, then all remainders will come.
Otherwise, let $x=(n\bmod{a})$.
We can find the summation till $i=n-x$ easily as it is multiple of $a$.
But now how do I find the summation from $(n-x+1)$ to $n$.
