Prove that [a/b]+[2a/b]+....+[(b-1)a/b]=(a-1)(b-1)/2

[Titan97]

Homework Statement

Prove that $$\sum_{r=1}^{b-1}[\frac{ra}{b}]=\frac{(a-1)(b-1)}{2}$$ where [.] denotes greatest integer function and a & b have no common factors.

Homework Equations

$n\le [n]<n+1$
<x> denotes fractional part of x.

3. The Attempt at a Solution
I first added and subtracted $a/b + 2a/b +3a/b +...+(b-1)a/b$ to get:
$$\frac{a(b-1)}2-\sum_{r=1}^{b-1}<\frac{ra}{b}>$$ where <.> denotes fractional part. This way I got closer to the answer. Also, <x> is a periodic function and it would be better to convert [.] to <.>. But I am stuck at this step.

 

[mfb]

It can be interesting to have a look at
$$\sum_{r=1}^{b-1}<\frac{ra}{b}> + \sum_{r=1}^{b-1}<\frac{b-ra}{b}>$$

 

[Titan97]

$\frac{b-ra}{b}=1-\frac{ra}{b}$.
The sum will be b-1

 

[mfb]

Sure. The two sums are the same if you transform one of them, so both contribute (b-1)/2.

 

[Titan97]

That solves the problem. But how did you do that post #2 magic? Did it pop in your mind when you saw the question? Or have you come across problems like these before? Is it because of practice?

 

[mfb]

The sum runs over all remainders of n/b, and it does so in a symmetric way.
That trick is not so uncommon.