<s>[INST] Evaluation of the sum $\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor$ Let $a, b$ and $c$ be positive integers. Recall that the greatest common divisor (gcd) function has the following representation:
\begin{eqnarray}
\textbf{gcd}(b,c) = 2 \sum_{k = 1}^{c- 1} \left \lfloor \frac{kb}{c} \right \rfloor + b + c - bc
\end{eqnarray}
as shown by Polezzi, where $\lfloor \cdot \rfloor$ denotes the floor function. In trying to generalize the formula I came across the following summation
\begin{eqnarray}
\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor.
\end{eqnarray}
I can prove the following identity for real $x$,
\begin{eqnarray}
\sum_{k = 0}^{c-1} \left \lceil \frac{x - kb}{c} \right \rceil = d \left \lceil \frac{x}{d} \right \rceil - \frac{(b-1)(c-1)}{2} - \frac{d-1}{2},
\end{eqnarray}
where $\lceil \cdot \rceil$ denotes the ceiling function and $d = \text{gcd}(b,c)$. (Note that in the first summation the upper index is in general independent of $c$.) Ideas or reference suggestions are certainly appreciated. Thanks in advance! 
Update I can prove the identity
\begin{eqnarray}
\sum_{k = 0}^{c-1} \left \lfloor \frac{x - kb}{c} \right \rfloor = d \left \lfloor \frac{x}{d} \right \rfloor - \frac{(b+1)(c-1)}{2} + \frac{d-1}{2},
\end{eqnarray}
where $d = \text{gcd}(b,c)$. There is another identity which might be useful. If $n = c \ell +r$ with $0 \leq r < c$, then
\begin{eqnarray}
\sum_{k = 1}^{n} \left \lfloor \frac{k}{c} \right \rfloor = c \binom{\ell}{2} + (r + 1) \ell.
\end{eqnarray}
Update 2 Ok, so I can prove that for real $x, y > 0$,
\begin{eqnarray}
\sum_{k = 0}^{\lfloor y \rfloor} \left \lfloor x + \frac{k}{y} \right \rfloor = \lfloor xy + (\lceil y \rceil - y) \lfloor x + 1 \rfloor \rfloor + \chi_{\mathbb{N}}(y)(\lfloor x \rfloor + 1),
\end{eqnarray}
where $\chi_{\mathbb{N}}$ denotes the characteristic function of the positive integers. My original problem (and a nice generalization of it) will be in hand if I can evaluate the following minor generalization: For real $x, y  > 0$ and $n \in \mathbb{Z}_{\geq 0}$,
\begin{eqnarray}
\sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor.
\end{eqnarray}
Again, any help is certainly appreciated!
 [/INST] 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.$$
</s>