# 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

-
@kahen: Thanks for the edit. –  Chan Feb 28 '11 at 7:08

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.

-
Many thanks. I will try this formula ;) –  Chan Feb 28 '11 at 6:53

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.

-
I think Chan was looking for hints rather than a complete solution. –  Yuval Filmus Feb 28 '11 at 7:41
@Yuval: That is probably true, especially since he accepted your answer. I couldn't think of any good way to hint towards this. –  Eric Naslund Feb 28 '11 at 15:55

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.

-