Skip to main content
4 of 4
added 156 characters in body

Closed form for sum of modulo remainders

Given a set of natural numbers {$N_1, ...N_n$} and another natural number $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 don't have any formal proof that a closed form can exist, but belief that one could exist has driven be into looking for a solution. I have been looking up several research papers and questions posted here, but could not get any pointers. Any help is greatly appreciated.