How does summation formula work with floor function? 
Prove that if a and b are relatively prime, then
  $$\sum_{n=1}^{a-1} \left\lfloor \frac{nb}{a}\right\rfloor = \frac{(a - 1)(b - 1)}{2}$$

My attempt was:
We have:
$$\sum_{i=1}^{n-1} i = \frac{n(n - 1)}{2}$$
Then, 
$$\sum_{n=1}^{a-1} \left\lfloor \frac{nb}{a}\right\rfloor = \left\lfloor \frac{a(a - 1)b}{2a}\right\rfloor$$
Could I apply the summation formula for floor function like above? Am I in the right track?  
Thanks,
Chan
 A: No, that doesn't work - it's just not true, since in general $\lfloor x + y \rfloor \neq \lfloor x \rfloor + \lfloor y \rfloor$, e.g. try $x=y=0.6$.
We have the general formula $$\left\lfloor \frac{x}{y} \right\rfloor = \frac{x-(x \mod{y})}{y}.$$ You can calculate the same using this formula.
A: Notice for each $n$ $$\left\lfloor\frac{nb}{a}\right\rfloor=\frac{nb}{a}-\frac{r_n}{a}$$ where $r_n\equiv nb \pmod a$ and $0\leq r_n< a$.  
Then since $a$ and $b$ are relatively prime, $nb\equiv mb \pmod a$ implies $n\equiv m \pmod a$ so that we conclude each remainder $r_n$ is unique.  But, we know $r_n\in \{1,2,\dots,a-1\}$ for each $n$, and since there are $a-1$ different values for $n$ we see that $r_n$ takes on each of these values.  Hence $$\sum_{i=1}^{a-1}r_i=\sum_{i=1}^{a-1}i=\frac{a(a-1)}{2}.$$
Then our original sum is 
$$\sum_{n=1}^{a-1} \left\lfloor \frac{nb}{a}\right\rfloor = \sum_{n=1}^{a-1} \frac{nb}{a}-\sum_{n=1}^{a-1}\frac{r_n}{a}=\frac{a(a - 1)b}{2a}-\frac{a(a-1)}{2a}=\frac{(a - 1)(b-1)}{2}$$ as desired.
A: A different Hint:
Consider a square of side $ab$, with one corner at $(0,0)$ and the opposite corner at $(ab, ab)$. Draw the vertical lines $x = b$, $x=2b$ etc and the horizontal lines $y = a$, $y = 2a$ etc.  Now try to count in two different ways, the number of intersection points of these lines, which lie on or below the diagonal of the square.
