Proof $\sum_{k=1}^{p-1}\left\lfloor\dfrac{km}{p}\right\rfloor=\dfrac{(m-1)(p-1)}{2}$ with $m$ and $p$ co-prime numbers

Question

We want to that: $$\sum_{k=0}^{p-1}\left\lfloor\dfrac{km}{p}\right\rfloor=\dfrac{(m-1)(p-1)}{2}$$ with the following conditions: $$\begin{cases}p\geqslant1,\ m\geqslant2, \\ m\text{ is even},\\ m\text{ and }p\text{ are co-prime.}\end{cases}$$

Answer 1

Let $q_k, r_k$ be the quotient and remainder of the euclidean division of $mk$ by $p$, ie $$mk = pq_k + r_k \text{ for } k\in[1, p-1]\quad \text{and } 0\le r_k\lt p$$

Now working mod $p$, since $r_1$ is coprime with $p$, it generates $\Bbb Z_p$ and therefore : $$\{r_k, k\in[1, p-1]\} = [1, p-1]$$

Notice we are trying to compute $$\begin{align}\sum_{k=1}^{p-1} q_k &= \sum_{k=1}^{p-1} {mk-r_k\over p} \\&= m{p(p-1)\over 2p} - \sum_{r=1}^{p-1}{r\over p} \\&= {m(p-1)\over2} - {p-1\over 2} \\&= {(p-1)(m-1)\over 2}\end{align}$$

Note : Using induction on this particular problem is not a good idea since $$\left\lfloor{m\over p}\right\rfloor \text{ and } \left\lfloor{m\over p+1}\right\rfloor$$ are not connected.

Answer 2

$$m-1<\bigg[\dfrac{m(p-1)}p\bigg]+\bigg[\dfrac1p\bigg]<m$$ $$→\bigg[\dfrac{m(p-1)}p\bigg]+\bigg[\dfrac1p\bigg]=m-1$$ This leads $$\sum_{k=0}^{p-1}\bigg[\dfrac{km}p\bigg]=\dfrac{(m-1)(p-1)}2$$