000RM.dvi

110 Lattice points

2.1 Counting interior points of a lattice triangle ....

A lattice triangle has vertices at(0,0),(a,0), and(a, b).

a

b

a

Counting in two ways, we obtain as

∑a−^1

n=

⌊

nb

a

⌋

=

∑b−^1

m=

⌊ma

b

⌋

.

Note that each of these is the total number of interior points and those on
the hypotenuse (except the two vertices). There aregcd(a, b)− 1 points
in the latter group.
If we put these two copies together to form a rectangle, we see that the
interior points along the diagonal are counted twice. Since the rectangle
has(a−1)(b−1)interior points, we have exactly

(a−1)(b−1)−gcd(a, b)+
2
lattice points in the interior of the triangle.

a

b

In particular, ifgcd(a, b)=1, then the triangle has^12 (a−1)(b−1)
interior points.
Note that we have an algorithm for computing the gcd of two integers:

gcd(a, b)=

∑b−^1

m=

⌊ma

b

⌋

−(a−1)(b−1) + 1.