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 .
- 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
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,
- Proof. To derive the result analytically, first, by counting in the other direction we have,
Proof. The proof is by induction. If then on the left we have
On the right,
So, indeed, the formula holds for the case .
Assume then that the formula is true for some . Then,
Thus, the formula holds for ; and thus, for all
This implies the sum is proportional to with constant of proportionality 2.
The proof is by induction. For the case
we have, on the left,
On the right we have . Hence, the formula holds for this case.
Assume then that the formula holds for some . Then,
Thus, if the statement is true for then it is true for . Hence, we have established the statement is true for all
We follow a similar strategy to this one
. From here
, and here
Then, since and by the telescoping property , we have,
, and the from the telescoping property we have,
So, using the additivity and homogeneity properties of finite sums, we have,
But, we know that and we know . So,
we know that
and from here, that
By additivity and homogeneity of finite sums we have,