Prove that$[{a\over b}]$+$[{2a\over b}]$+$[{3a\over b}]$+...+$[{(b-1)a\over b}]$ = $(a-1)(b-1)\over2$

Question

If a and b are positive integers with no common factor how to show that $[{a\over b}]$+$[{2a\over b}]$+$[{3a\over b}]$+...+$[{(b-1)a\over b}]$ = $(a-1)(b-1)\over2$,where [.] denotes the greatest integer function? I'm not able to understand how to simplify the LHS to RHS. Help please!!

Answer 1

If $x,y\not\in\mathbb{Z}$ and $x+y\in\mathbb{Z}$, then $\left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor=x+y-1$. Therefore, $$ \left\lfloor j\frac ab\right\rfloor+\left\lfloor(b-j)\frac ab\right\rfloor=a-1\tag{1} $$ If $(a,b)=1$, then for $0\lt j\lt b$, we have $j\frac ab\not\in\mathbb{Z}$.

Summing $(1)$, we get $$ \sum_{j=1}^{b-1}\left\lfloor j\frac ab\right\rfloor+\left\lfloor(b-j)\frac ab\right\rfloor=(a-1)(b-1)\tag{2} $$ $(2)$ counts each term in the sum we want twice, so we get $$ \sum_{j=1}^{b-1}\left\lfloor j\frac ab\right\rfloor=\frac{(a-1)(b-1)}2\tag{3} $$

Answer 2

The sum of the integer parts equals the sum of the original numbers, minus the sum of the fractional parts.
What is the sum of the fractional parts? Hint: They are $1/b,2/b,...,(b-1)/b$ in some order.

Answer 3

HINT: Count the number of lattice points of the form $(m,n)$ below the line $by=ax$, where $1 \leq m < b$. This should be half the number of lattice points inside the rectangle with vertices at $(0,0),(a,0),(a,b),(0,b)$, since $\gcd(a,b) = 1$.

Answer 4

$

Consider the triangle formed by the three points $O=(0, 0),\; A=(b, 0),\;$ and $B=(b, a)$. The line $OA$ has equation y = $\frac{a}{b}x$. Put a dot at all of the points strictly inside of the triangle $OAB$. This will provide a rectangular lattice of points. The number $\lfloor \frac{na}{b} \rfloor$ is equal to the number of points in the triangle between $(n, 0)$ and $(n, \frac{na}{b})$. Hence $\sum_{n=1}^{b-1} \lfloor \frac{na}{b} \rfloor$ counts, columnwise, the number of lattice points in the interior of the triangle.

If $\frac{a}{b}$ is in lowest terms, there will be no lattice points on the line strictly between points $O$ and $B$. So we can make triangle $OBA'$ where $A' = (0, a)$ and the two triangle together will form rectangle $OABA'$. Which contains exactly (a-1)(b-1) lattice points. Since there are no lattice points on the interior of segment $OB$, it follows that

$$\sum_{n=1}^{b-1} \left\lfloor \frac{na}{b} \right\rfloor = \frac{(a-1)(b-1)}{2}$$

As an added bonus, note that $\sum_{n=1}^{a-1} \lfloor \frac{nb}{a} \rfloor$ counts, rowwise, the number of lattice points in the interior of triangle $OBA'$. It follows that

$$\sum_{n=1}^{b-1} \left\lfloor \frac{na}{b} \right\rfloor = \sum_{n=1}^{a-1} \left\lfloor \frac{nb}{a} \right\rfloor = \frac{(a-1)(b-1)}{2}$$

Answer 5

This is a duplicate of this: How do I prove that $\sum_{k=1}^{b-1} [k \frac{a}{b}] = \frac{(a-1)(b-1)}{2}$?

That is a link to my answer. To quote it:

This sum comes up in Gauss' proof of the law of quadratic reciprocity.

Eisenstein's nice geometric proof is in many places; here is one: http://en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity