Proof for $\sum_{x=1}^{n-1}\left\lfloor \dfrac{mx}{n}\right\rfloor=\dfrac{(n-1)(m-1)}{2}$ where $(m,n)=1$

Question

This identity might be well-known, but I could find the proof neither by myself not by searching it in Internet. Could you describe an outline of solution?

Answer 1

Note that $$x\mapsto mx-n\lfloor mx/n\rfloor=mx\,({\rm mod~}{n})$$ is a permutation of the integers $\{1,2,\ldots,n-1\}$ because $(n,m)=1$. So $$ \sum_{x=1}^{n-1}\left( mx-n\left\lfloor\frac{mx}{n}\right\rfloor\right)= \sum_{k=1}^{n-1}k=\frac{n(n-1)}{2} $$ that is $$ m\frac{n(n-1)}{2}-n\sum_{x=1}^{n-1}\left\lfloor\frac{mx}{n}\right\rfloor=\frac{n(n-1)}{2} $$ which is equivalent to the desired result.