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
Best Answer
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.