Let me answer how
this formula is valid.
When N and M are coprimes then Ni and Nj cannot leave same remainder with M for 0<i,j<M-1.
If they leave the same remainder that implies that abs(N*(i-j)) is a multiple of M, as (i-j)<M hence N and M must have a common factor greater than 1. This contradicts our initial hypothesis that their g.c.d is 1.
Now for any N and M, let the gcd be g.
let N = g*k1 and M = g*k2.
g.c.d(k1,k2) should be 1.
The situation here is similar to the situation when N and M are coprimes.
For example lets consider N=10 and M=6 => g(gcd)=2 k1=5 k2=3.
The remainders we are going to get are 0 4 2 0 4 2.
0 4 2 is the repeating sequence. This can be rewritten as 0*g 1*g … (k2-1)*g because k1 and k2 are coprimes. There are k2 remainders in each such repeating sequence. As the total length is k2*g, hence there must be g such repeating sequences.
So in general the sum of the remainders is
sum_remainders = g*g*sigma[i from 0 to k2-1].
total_sum = N*sigma[i from 0 to M-1] is N*M*(M-1)/2.
We have to subtract the sum of remainders from total_sum to get the sum of quotients*M.
total_sum-sum_remainders = ((N-1)*(M-1)+g-1)/2.
Hence the proof.