# Number of Lattice Points in a Triangle

Problem

Let the co-ordinates of the vertices of the $\triangle OAB$ be $O(1,1)$, $A(\frac{a+1}{2},1)$ and $B(\frac{a+1}{2},\frac{b+1}{2})$ where $a$ and $b$ are mutually prime odd integers, each greater than $1$. Then find the number of lattice points inside $\triangle OAB$, i.e., not on the borders of $\triangle OAB$. How does the answer change if the restriction $\operatorname{gcd}(a,b)=1$ is removed?

Solution

Let $L(a,b)$ be the number of lattice points inside $\triangle OAB$. The linear transformation $T(x,y)=(x-1,y-1)$ on the triangle $OAB$ do not have any effect on $L(a,b)$. Hence $L(a,b)$ is equal to the number of lattice points inside the triangle $O'A'B'$, where $O'=(0,0)$, ${\textstyle A'=(\frac{a-1}{2},0)}$ and ${\textstyle B'=(\frac{a-1}{2},\frac{b-1}{2})}$.

Set ${C'=(0,\frac{b-1}{2})}$. By symmetry the number of lattice points inside the rectangle $O'B'C'$ is $L(a,b)$. The number of lattice point inside the rectangle $O'A'B'C'$ is ${\textstyle \frac{a-3}{2} \cdot \frac{b-3}{2}}$. Consequently

$$2L(a,b) = \frac{a-3}{2} \cdot \frac{b-3}{2} - K$$

where $K$ are the number of lattice points on the straight line between $O'$ and $B'$. This line is given by $y= \frac{b-1}{a-1}x$, yielding

$$K = |\{ {\textstyle 0 < x < \frac{a-1}{2} \mid \frac{b-1}{a-1}x \in \mathbb{N} \}| }$$

By letting $d=\text{gcd}(a-1,b-1)$, we obtain $a-1=rd$ and $b-1=sd$ for two positive coprime integers $r$ and $s$. Therefore

$$\frac{b-1}{a-1}x = \frac{sx}{r} \in \mathbb{N} \;\; \Leftrightarrow \;\; \frac{x}{r} \in \mathbb{N}$$

Now ${\textstyle 0 < x < \frac{a-1}{2} = \frac{rd}{2}}$, implying ${\textstyle 0 < \frac{x}{r} = \frac{d}{2}}$. Since $d$ is even (since $d=\gcd(a-1,b-1)$ and $a$ and $b$ are both odd positive integers) give us ${\textstyle K = \frac{d}{2}-1}$. Thus by (1)

$${\textstyle L(a,b) = \dfrac{(a-3)(b-3)}{8} - \dfrac{\text{gcd}(a-1,b-1)}{4} + \dfrac{1}{2}}$$

But I think that by Pick's Theorem the answer should be,

$${\textstyle L(a,b) = \dfrac{(a-1)(b-1)}{8} - \dfrac{\text{gcd}(a-1,b-1)}{4} + \dfrac{1}{2}}$$

Which one is correct?

• You can easily figure out which one is correct by putting in some small values for $a$ and $b$. – Ted Sep 14 '14 at 6:06
• Try $a = 1$ and $b = 10$. This yields a degenerate triangle with $0$ lattice points strictly inside it. Which answer gives you $0$? – JimmyK4542 Sep 14 '14 at 6:17
• @JimmyK4542: Both $a$ and $b$ are odd and mutually prime and each is greater than $1$. – user170039 Sep 14 '14 at 6:26
• Fine, try a less trivial case like $a = 3$ and $b = 5$. The formula in the gray box gives $L(3,5) = 0$ while the other formula gives $L(3,5) = 1$. Which one is right? – JimmyK4542 Sep 14 '14 at 6:27
• There are $0$ lattice points inside the triangle with vertices $O(1,1)$, $A(2,1)$, $B(2,3)$. So the first formula is correct (in that case). I have no idea where the second formula goes wrong because you have left out the details of how you got that. – JimmyK4542 Sep 14 '14 at 6:34

The area of $\Delta OAB$ is $K = \dfrac{1}{2} \cdot \dfrac{a-1}{2} \cdot \dfrac{b-1}{2} = \dfrac{(a-1)(b-1)}{8}$.

The number of points on the boundary (line segments $OA$, $AB$, and $BO$) is

$\underbrace{\dfrac{a-1}{2}}_{OA}+\underbrace{\dfrac{b-1}{2}}_{OB}+\underbrace{\text{gcd}\left(\dfrac{a-1}{2},\dfrac{b-1}{2}\right)}_{BO}$ (you missed the first two terms of this).

So, by Pick's Theorem, the area is

$K = I+\dfrac{1}{2}B-1 = I+\dfrac{1}{2}\left[\dfrac{a-1}{2}+\dfrac{b-1}{2}+\text{gcd}\left(\dfrac{a-1}{2},\dfrac{b-1}{2}\right)\right]-1$

$= I + \dfrac{a-1}{4} + \dfrac{b-1}{4}+\dfrac{\text{gcd}(a-1,b-1)}{4}-1$.

Hence, the number of points in the interior is

$I = \dfrac{(a-1)(b-1)}{8} - \dfrac{a-1}{4} - \dfrac{b-1}{4} - \dfrac{\text{gcd}(a-1,b-1)}{4} + 1$

$= \dfrac{(a-3)(b-3)}{8} - \dfrac{\text{gcd}(a-1,b-1)}{4} + \dfrac{1}{2}$ (after a bit of simplification).