6
$\begingroup$

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

  • 0
    @kahen: Thanks for the edit.2011-02-28

3 Answers 3

5

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.

  • 0
    Many thanks. I will try this formula ;)2011-02-28
4

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.

  • 0
    @Yuv$a$l: That is probably true, especially since he accepted your answer. I couldn't think of any good way to hint towards this.2011-02-28
2

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.