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

Tags:
1. Aug 8, 2015

### Titan97

1. The problem statement, all variables and given/known data
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.

2. Relevant 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.

2. Aug 8, 2015

### Staff: Mentor

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}>$$

3. Aug 8, 2015

### Titan97

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

4. Aug 8, 2015

### Staff: Mentor

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

5. Aug 8, 2015

### 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?

6. Aug 8, 2015

### Staff: Mentor

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