Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Look at Eisenstein's proof in 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.… – 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
up vote 5 down vote accepted

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.

share|cite|improve this answer
Thanks for showing me a number theoretical solution. I think I can utilize this method to other similar questions. – Math.StackExchange Jun 5 '14 at 20:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.