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

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?

-
Look at Eisenstein's proof in en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity for a geometric interpretation of that sum as an area. – KCd Jun 5 '14 at 10:40
I see. So, the symmetry about the diagonal line tells the answer. It's quite interesting. – Math.StackExchange Jun 5 '14 at 10:49
Alternatively, see "Concrete Mathematics" by Graham, Knuth, Patashnik. Chapter 3, it deals with sums involving floor/frac etc. More specifically this is a special case of Eq. 3.32, pp 96. matematica.net/portal/e-books/… – Graham Hesketh Jun 5 '14 at 10:57
I actually wanted to read that book after reading the books which I'm currently reading. I appreciate you for showing the link to the pdf. – Math.StackExchange Jun 5 '14 at 10:59

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.