Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@kahen: Thanks for the edit. –  Chan Feb 28 '11 at 7:08

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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