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 be relatively prime positive integers (i.e., they have no common factors other than 1). Then we have the formula The sum is 0 when .

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 Further, from this exercise (1.7, #4), we know 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 Thus, we have, 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, 2. Proof. To derive the result analytically, first, by counting in the other direction we have, Then, 