Skip to main content
1 of 4

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$
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.