Let $p, q$ be co-prime natural numbers. Show that they satisfy : $$\sum_{k=1}^{q-1}\left\lfloor\frac{kp}{q}\right\rfloor=\sum_{k=1}^{p-1}\left\lfloor\frac{kq}{p}\right\rfloor=\frac{(p-1)(q-1)}{2}$$
There exists a proof using lattice points.
But I would like to see a normal proof using the basic way of solving integer functions like taking $\left\lfloor\frac{p}{q}\right\rfloor = x$, i.e, $p=qx+r \ni r < x$ and then substitution or whatsoever.
In case someone is interested in the lattice proof, here it goes:
Consider a the lattice points with $1\leq x \leq q-1, 1\leq y \leq p-1$. They lie inside the rectangle $OABC$ where $O$ is the origin, $OA=x-\text {axis}$ and $OB=y-\text {axis}$. Here, $|OA|=q, |OC|=p$. None of the considered lattice points $\in$ diagonal $OB$. This would contradict $\gcd(p,q)=1$. We doing the number of lattice points below $OB$ in two ways:
1) $\text {Their count is } \dfrac{1}{2}(p-1)(q-1)$
2) $\text {It equals} \displaystyle\sum_{k=1}^{q-1}\left\lfloor\frac {kp}{q}\right\rfloor$
Best Answer
Suppose that $q$ is odd and $q=2n+1$. For $k$ a positive integer let \begin{eqnarray*} kp \equiv j \pmod{q} \end{eqnarray*} with $0<j<q$ (and $0<q-j<q$) so $kp=j+lq $ (for some $l$) and $ \left \lfloor \frac{kq}{q} \right \rfloor =l$.
Now $(2n-k)p = (p-l-1)q +q-j $ so $ \left \lfloor \frac{(2n-k)q}{q} \right \rfloor =p-l-1$.
\begin{eqnarray*} \sum_{k=1}^{2n} \left \lfloor \frac{kq}{q} \right \rfloor= \sum_{k=1}^{n} \left(\left \lfloor \frac{kq}{q} \right \rfloor+ \left \lfloor \frac{(2n-k)q}{q} \right \rfloor \right)= n(p-1). \end{eqnarray*}