Let 
be relatively prime positive integers (i.e., they have no common factors other than 1). Then we have the formula
![\[ \sum_{n=1}^{b-a} \left[ \frac{na}{b} \right] = \frac{(a-1)(b-1)}{2}. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-bf9d896e83f8c857f8a076ee5f250dca_l3.png "Rendered by QuickLaTeX.com")
The sum is 0 when 
.
- Prove this result by a geometric argument.
- Prove this result by an analytic argument.
- Proof. We know by the previous exercise (1.11, #6) that
![\[ \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \begin{array}{l} \text{\# of lattice points inside a right triangle}\\ \text{of base } b \text{ and height } a \ (\text{letting } f(x) = \frac{ax}{b}).\end{array} \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-0689f078dabfe2f9a7e99e9d8c78712c_l3.png "Rendered by QuickLaTeX.com")
Further, from this exercise (1.7, #4), we know
![\[ a(T) = I_T + \frac{1}{2} B_T - 1 \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-35b980dd9d980c30a580cecd9e5d8af5_l3.png "Rendered by QuickLaTeX.com")
where
number of interior lattice points, and 
number of boundary lattice points. We also know by the formula for the area of a right triangle that![\[ a(T) = \frac{1}{2} (ab). \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-67f02756e7466afe59efb284251e33ed_l3.png "Rendered by QuickLaTeX.com")
Thus, we have,
![\[ I = \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \frac{1}{2} (ab) - \frac{1}{2}B_T + 1. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-a0914ed2e6bca09bfd7891cd6e374637_l3.png "Rendered by QuickLaTeX.com")
Then, to calculate
we note there are no boundary points on the hypotenuse of our right triangle (since 
and 
have no common factor). (This follows since if there were such a point then 
for some 
, but then we would have divides , contradicting that they have no common factor.) Thus, 
. So,![\begin{align*} \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (ab) - \frac{1}{2} (a+b+1) +1 \\ &= \frac{1}{2} (ab - a - b + 1) \\ &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-886c5d307be7a0899d33477b06b51695_l3.png "Rendered by QuickLaTeX.com")
- Proof. To derive the result analytically, first, by counting in the other direction we have,
![\[ \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right]. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-29c81c170d3a533fdf4e7d84907b4d18_l3.png "Rendered by QuickLaTeX.com")
Then,
![\begin{align*} && \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] - \sum_{n=1}^{b-1} 1 \\ \implies && 2 \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} 1 = (b-1)a - (b-1)\\ \implies && \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-e5a232476ce2a6f8970dba437cd3a552_l3.png "Rendered by QuickLaTeX.com")
In the (b) part where does this “-1” term come from?
From Ex 4(b). Since a and b have no common factors, we can only have na/b be an integer when n is a multiple of b, but 0<n<b. Thus, [-na/b] = -[na/b]-1.
If na is divisible by b for some integer n (1<= n <=b), we can only conclude that a and b share some common factors greater than 1, not a divides b (I think you mean a is divisible by b in this case).