Home » Lattice Points

# 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, # Formula for counting lattice points in the ordinate set of a function

For a nonnegative function defined on an interval define the set (i.e., the region enclosed by the graph of the function and the -axis between the vertical lines at and ). Then prove where is the greatest integer less than or equal to .

We can help ourselves by drawing a picture to get a good idea of what is going on, then turn that intuition into something more rigorous. The picture is as follows: In the picture, we can see the number of lattice points in the ordinate set of (not including the -axis since the question stipulates contains the points ). At each integer between and , we count the number of lattice points beneath , the greatest integer less than or equal to . Then we need to turn this intuition from the picture into a proof:

Proof. Let with . We know such an exists since with . Then, the number of lattice points in with first element is the number of integers such that . But, by definition, this is (the greatest integer less than or equal to ). Summing over all integers we have, # Prove that no equilateral triangle can have all of vertices on lattice points

Prove that an equilateral triangle cannot have all of vertices on lattice points, i.e., points such that both are integers.

Proof. Suppose there exists such an equilateral triangle . Then, for two disjoint, congruent right triangles . Since the vertices of are at lattice points, we know the altitude from the vertex to the base must pass through lattice points (where is the height of ). Therefore, denoting the lattice points on this altitude by , we have Since is a polygon with lattice point vertices we know by the previous exercise, that . Further, by Exercise #2 of this section, we know . So, But, , so, But, , so this is a contradiction. Therefore, cannot have its vertices at lattice points and be equilateral 