Evaluation of the sum $\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor$

Here is an observation/partial result. For brevity write $t = \lfloor a/b \rfloor .$ When $\text{gcd}(b,c)=1$ and $c \, | \, (t+1) $ we have

$$ S = \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-1}{2} \right \rbrace . $$

Proof:

Suppose

$$\begin{align} a &= m_0 c + r_0 \\ a- b &= m_1 c + r_1 \\ a - 2b &= m_2 c + r_2 \\ \cdots &= \cdots \\ a - tb &= m_t c + r_t \end{align}$$

for integer $m_i$ and $r_i$ where $ 0 \le r_i < c $ then, adding the above equations,

$$(t+1)a - \frac{t(t+1)}{2}b = Sc + \sum_{k=0}^t r_k . \quad (1)$$

Now if $\text{gcd}(b,c)=1$ and $k$ runs over a complete system of residues modulo $c$ then $a-kb,$ where $a$ is any integer, also runs over a complete system of residues modulo $c$. So when $ c \, | \, (t+1) $ we have that $a-kb$ runs over $(t+1)/c$ complete residue systems modulo $c$. Hence $$\sum_{k=0}^t r_k = \frac{(t+1)(c-1)}{2}.$$

Substitute this into $(1)$ to obtain the result.

EDIT: Here is a generalisation for the case $\text{gcd}(b,c)>1,$ which reduces to the above when $b$ and $c$ are coprime.

Write $d=\text{gcd}(b,c)$ and suppose $ a \equiv \lambda \textrm { mod } d $ where $ 0 \le \lambda < d.$

Now $a-kb$ runs through all the residues modulo $c$ that are congruent to $ \lambda $ modulo $c$ as $k$ runs through $0,1,2,\ldots,u-1$ where $u=c/d.$ When $ u \, | \, (t+1) $ we have that $r_0,r_1,\ldots,r_t$ runs through $(t+1)/u$ such residue systems. Hence

$$ \sum_{k=0}^t r_k = \frac{t+1}{u} \left \lbrace \frac{du(u-1)}{2} + \lambda u \right \rbrace = (t+1) \left \lbrace \frac{c-d}{2} + \lambda \right \rbrace .$$

And so

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-d}{2} - \lambda \right \rbrace . $$

EDIT2: Here are a couple of numerical examples. With $a=91,b=15 \textrm{ and } c=21$ we have $d=\text{gcd}(15,21)=3,$ $t=\lfloor 91/15 \rfloor = 6,$ $u=c/d=21/3=7$ and $91 \equiv 1 \textrm{ mod } 3,$ and so $\lambda=1.$ Note that the condition $ u \, | \, (t+1)$ is satisfied. Our formula gives the sum as

$$\frac{7}{21} \left \lbrace 91 - \frac{6 \cdot 15}{2} - \frac{21-3}{2} - 1 \right \rbrace = 12.$$

This is small enough to check by hand.

$$ \sum_{k=0}^7 \left \lfloor \frac{91-15k}{21} \right \rfloor = 4+3+2+2+1+0+0=12.$$

With $a=703,b=35 \textrm{ and } c=49$ we have $d=\text{gcd}(35,49)=7,$ $t=\lfloor 703/35 \rfloor = 20,$ $u=c/d=49/7=7$ and $703 \equiv 3 \textrm{ mod } 7,$ and so $\lambda=3.$ Note that the condition $ u \, | \, (t+1)$ is satisfied. Our formula gives the sum as

$$\frac{21}{49} \left \lbrace 703 - \frac{20 \cdot 35}{2} - \frac{49-7}{2} - 3 \right \rbrace = 141.$$

One can verify with WolframAlpha, or similar, that

$$ \sum_{k=0}^{20} \left \lfloor \frac{703-35k}{49} \right \rfloor = 141.$$

I would like to summarise and extend the results of my previous answer in a new answer as I prefer to keep the original in its current form to prevent it from turning into my magnum opus.

Theorem 1:

For positive integers $a, b$ and $c$ where $ d=\text{gcd}(b,c), $ $u=c/d,$ $t= \lfloor a/b \rfloor $ and $ a \equiv \lambda \textrm{ mod } d, $ where $ 0 \le \lambda < d,$ and $ u \, | \, (t+1) $ we have

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-d}{2} - \lambda \right \rbrace . $$

So far, the above theorem and its proof are included in my previous answer. The rest is new.

Theorem 2:

Along with the definitions in theorem 1, let $ a \equiv r \textrm{ mod } c, $ where $ 0 \le r < c $ and $ u \, | \, t $ then

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{r}{c} . $$

For example, with $a=1019,b=33$ and $c=55$ we have $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1019/33 \rfloor = 30$ and $ 1019 \equiv 29 \textrm{ mod } 55, $ and $ 1019 \equiv 7 \textrm{ mod } 11. $ Hence $ r = 29 $ and $\lambda = 7.$

Note that the condition $ u \, | \, t $ is satisfied, and so theorem 2 gives

$$ \sum_{k=0}^{30} \left \lfloor \frac{1019 - 33k}{55} \right \rfloor = \frac{31}{55} \left \lbrace 1019 - \frac{ 30 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 7 \cdot 5 \right \rbrace - \frac{29}{55} = 279.$$

This is easily verified with WolframAlpha, or similar.

Both of these theorems are special cases ($ \mu=0$ and $\mu=1$) of the general result:

Theorem 3: Along with the previous definitions in theorems 1 and 2, let $ t+1 \equiv \mu \textrm{ mod } u,$ where $ 0 \le \mu < u $ then

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace $$ $$ - \frac{1}{c} \sum_{k=0}^{\mu - 1} \left \lbrace r+k \left \lbrace \left( \left \lfloor \frac{b}{c} \right \rfloor + 1 \right) c - b \right \rbrace \textrm{ mod } c \right \rbrace .$$

There are $ \mu $ terms in the last sum, so this is understood to be zero when $ \mu =0.$ The terms in the final summation of the equation are all $ \ge 0 $ and reduced modulo $c.$

A sketch of the proof runs as follows. On adding up the $t+1$ equations at the start of my previous answer, we add up $ \lfloor (t+1)/u \rfloor $ “complete” sets of residues modulo $c$ (not to be confused with a complete residue system modulo $c$) that are congruent to $ \lambda $ modulo $c.$ The term $ \sum_{k=0}^{\mu - 1} \lbrace r+k \lbrace \cdots \rbrace \textrm{ mod } c \rbrace $ (equivalent, of course, to $ \sum_{k=0}^{\mu - 1} \lbrace (r-kb) \textrm{ mod } c \rbrace $ ) is the sum of the “left over residues.”

Rearranging the equation obtained from the summation proves the theorem.

Note: In the text $ \lbrace \cdot \rbrace $ is only used for readability and does not indicate fractional part (I find doubled-up curved brackets awkward to read).

Just for fun, here is what we get when we put $ \mu = 2 $ into theorem 3.

Theorem 2(b): Along with the previous definitions, since $ \mu = 2 $ our condition here is that $ u \, | \, (t-1) .$ Now for $ r \ge b $ we obtain

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{2r-b}{c} . \quad (1) $$

For example, with $a=1037,b=33$ and $c=55$ we have $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1037/33 \rfloor = 31$ and $ 1037 \equiv 47 \textrm{ mod } 55, $ and $ 1037 \equiv 3 \textrm{ mod } 11. $ Hence $ r = 47 $ and $\lambda = 3.$

Note that the condition $ u \, | \, (t-1) $ is satisfied, and so theorem 2(b) gives

$$ \sum_{k=0}^{31} \left \lfloor \frac{1037 - 33k}{55} \right \rfloor = \frac{32}{55} \left \lbrace 1037 - \frac{ 31 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 3 \cdot 5 \right \rbrace - \frac{2 \cdot 47 - 33}{55} = 291.$$

This is easily verified with WolframAlpha, or similar.

For $ r < b $ the final term in $(1)$ would be $ - \frac{2r+c-b}{c}.$

(To be continued... time and enthusiasm permitting :-) )