Sign up ×
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.

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. – MathOverStackExchange 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. – MathOverStackExchange Jun 5 '14 at 10:59

1 Answer 1

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. – MathOverStackExchange 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.