Number theory properties of floor function

Question

If $m$ and $n$ are coprime, prove that

$$\sum_{j=1}^{j=m-1}\left\lfloor\frac {jn} {m}\right\rfloor =\frac {(m-1) (n-1)}{2}$$

Answer 1

Hint: Note that $$\left\lfloor\frac {a}{b}\right\rfloor = \frac{a}{b} - \frac{a \pmod b}{b}.$$ Thus

\begin{eqnarray} \sum_{j=1}^{m-1} \left\lfloor\frac{jn}{m}\right\rfloor &=& \sum_{j=1}^{m-1} \frac{jn}{m} -\sum_{j=1}^{m-1} \frac{jn \pmod m}{m}\\ &=& \frac{n}{m}\sum_{j=1}^{m-1} j - \sum_{j=1}^{m-1} \frac{j}{m}\\ &=& \frac{n}{m}\frac{(m-1)m}{2} - \frac{1}{m}\frac{(m-1)m}{2}\\ &=& \frac{(n-1)(m-1)}{2} \end{eqnarray}

where the second equality holds since $\{jn \pmod m\}_{1 \le j \le m-1}$ is a permutation of $\{1,\ldots,m-1\} = \{j\}_{1 \le j \le m-1}$ (this is where coprime comes into play).