Home » Blog » Prove a formula for the sum of [(na)/b] where a,b are relatively prime integers

Prove a formula for the sum of [(na)/b] where a,b are relatively prime integers

Let a,b 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}. \]

The sum is 0 when b=1.

  1. Prove this result by a geometric argument.
  2. Prove this result by an analytic argument.

  1. 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} \]

    Further, from this exercise (1.7, #4), we know

        \[ a(T) = I_T + \frac{1}{2} B_T - 1 \]

    where I_T = number of interior lattice points, and B_T = 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). \]

    Thus, we have,

        \[ I = \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \frac{1}{2} (ab) - \frac{1}{2}B_T + 1. \]

    Then, to calculate B_T we note there are no boundary points on the hypotenuse of our right triangle (since a and b have no common factor). (This follows since if there were such a point then \frac{na}{b} \in \mathbb{Z} for some n < b, but then we would have a divides b, contradicting that they have no common factor.) Thus, B_T = a + b + 1. 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*}

  2. 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]. \]


        \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*}

One comment

  1. Anonymous says:

    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).

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):