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

$\endgroup$
  • $\begingroup$ @kahen: Thanks for the edit. $\endgroup$ – Chan Feb 28 '11 at 7:08
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Many thanks. I will try this formula ;) $\endgroup$ – Chan Feb 28 '11 at 6:53
4
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.