Skip to main content
2 of 4
added definition for $K$

Closed form for sum of modulo remainders

Given n distinct random positive integers {$N_0, ...N_n$}, find a closed form solution for the below sum

$M = \sum_{i=1}^n N_i \% N$
    where $N_i, N, n \in \mathbb N$
    and $N_i \% N$ is the remainder when $N_i$ is divided by $N$

Although trivial, I was able to reduce it to the below form

$M = KN + (\sum_{i=1}^n N_i)\%N$
   where $K$ is the quotient when $M$ is divided by N

but I am unable to reduce $K$ further into any closed form.

I have been looking up several research papers and questions posted here, but could not get any pointers. Any help is greatly appreciated.