Take the 2-minute tour ×
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|improve this question
1  
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 at 10:40
    
I see. So, the symmetry about the diagonal line tells the answer. It's quite interesting. –  Aran Komatsuzaki Jun 5 at 10:49
2  
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 at 10:57
1  
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. –  Aran Komatsuzaki Jun 5 at 10:59

1 Answer 1

up vote 4 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|improve this answer
    
Thanks for showing me a number theoretical solution. I think I can utilize this method to other similar questions. –  Aran Komatsuzaki Jun 5 at 20:17

Your Answer

 
discard

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.