<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] This isn't a complete solution but rather a reformulation for a large number of cases involving the problem above. Write $n = m \lfloor y \rfloor + r$, where $0 \leq r < \lfloor y \rfloor$ and $n, m , r \in \mathbb{Z}_{\geq 0}$. Then for real $x, y > 0$, we have
\begin{eqnarray}
\sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor & = & \lfloor x \rfloor + \sum_{\ell = 0}^{m-1} \left \lfloor x y + \ell \lfloor y \rfloor  + ( \lceil y \rceil - y) \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y} + 1  \right \rfloor   \right \rfloor +
\end{eqnarray}
\begin{eqnarray} & & \sum_{k = 1}^{r}  \left \lfloor   x + \frac{m \lfloor y \rfloor}{y}  + \frac{k}{y} \right \rfloor  +   \chi_{\mathbb{N}}(y) \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y}  + 1 \right \rfloor - \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{ \ell \lfloor y \rfloor }{y}  \right \rfloor .
\end{eqnarray}
This was derived by partitioning the interval $[0,n]$ into subintervals and using the last identity in the description of the problem.
For the original problem, write
\begin{eqnarray}
\sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{a - k b}{c} \right \rfloor = \sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{\text{mod}(a,b) + k b}{c} \right \rfloor
\end{eqnarray}
where $\text{mod}(a,b) = a - b \lfloor \frac{a}{b} \rfloor$. If $\lfloor \frac{a}{b} \rfloor \gg c$, then use the identity above to vastly reduce the number of terms in the sum.
</s>