# evaluation of the sum $\sum_{a=1}^{p-1} \left\lfloor \frac{\left\lfloor{v/p}\right\rfloor-a}{q}\right\rfloor$

Looking for the evaluation of the sum $$\sum_{a=1}^{p-1} \left\lfloor \frac{\left\lfloor{v/p}\right\rfloor-a}{q}\right\rfloor$$ where $p < q$, $p$ and $q$ are primes, and $v = (N \mod{p*q})$ where for integer $N \ge p * q$. Also $\left\lfloor{v/p}\right\rfloor \in \left\{{0, 1, 2, \ldots, q - 1}\right\}$. This sum will be negative

I just go the answer for the sum $$\sum_{a=1}^{p-1} \left\lfloor \frac{\left\lfloor{v/p}\right\rfloor+a}{q}\right\rfloor.$$ From this argument, then since $v < pq$, we have $-1< \lfloor v/p \rfloor - a <q$ for $a > \lfloor v/p \rfloor$, so each term is either $0$ or $-1$. A term is $-1$ iff $a$ is large enough: one needs $a > \lfloor v/p\rfloor$. But, also $a \le p - 1$.

Now I think that the sum is the number of integers in the interval $\left[ q-p+1,\lfloor v/p\rfloor +p-1 \right]$, which would lead to $$\min(0, \lfloor v/p\rfloor-(q-p)+(p-1)).$$ I have tested this and it hold up so far.

My question is the justification of this interval step $\left[ q-p+1,\lfloor v/p\rfloor +p-1 \right]$. Following the logic of the previous case this interval should be $\left[\lfloor v/p\rfloor + 1, p-1 \right]$ which leads (ignoring the sign) to $$\min(0, p - 1 - \lfloor v/p\rfloor).$$

• – rabota Apr 12 '18 at 21:39

## 1 Answer

Since $v < pq$, we have $-1< \lfloor v/p \rfloor - a <q$ for $a > \lfloor v/p \rfloor$, so each term is either $0$ or $-1$. A term is $-1$ iff $a$ is large enough: one needs $a > \lfloor v/p\rfloor$. So the sum is the negative of the number of integers in the interval $\left[\lfloor v/p\rfloor + 1, p - 1\right]$, which would lead to $$- \max(0, p - 1 -\lfloor v/p\rfloor) = \min(0, \lfloor v/p\rfloor - (p - 1)).$$