For $n$ prime, each of the remaining triangles contains exactly the same number of grid points.
This was proved here.
However, is the converse true i.e., triangles containing exactly the same number of grid points implies a prime? I tried (geometrically) finding a non-prime which had the same number of internal grid points, but the lattice became too noisy to accurately manage.
Thanks.
Best Answer
Let $n > 1$ be a positive integer and for each $0 \le i < n$, let $\Delta_n(i)$ be the triangle with coordinates at $(0,0)$, $(i,n-i)$ and $(i+1, n-(i+1))$.
Euclidean geometry tells us that these triangles have the same area since they have the same base and height if you take the base as the $((i,n-i), (i+1,n-(i+1)))$ edge and the height as the orthogonal segment to $((0,n), (n,0))$ that drops from the origin, namely the segment $((0,0), (n/2,n/2))$. So by Pick's theorem, denoting by $B_n(i)$ and $I_n(i)$ the number of grid points on the boundary and interior of $\Delta_n(i)$ respectively, we see that the quantity $2B_n(i) + I_n(i)$ must be constant when $i$ varies from $0$ to $n-1$ because $2B_n(i) + I_n(i) = 2 \, \mathrm{Area}(\Delta_n(i)) + 2$.
You'll notice two exceptions to the rule that the number of interior points remains the same, namely for the triangles $\Delta_n(0)$ and $\Delta_n(n-1)$; the problem with those two is that they share $n+1$ points with the $x$-axis (resp. $y$-axis) and one point at $(1,n-1)$ (resp. $(n-1,1)$), and no interior point. It doesn't help us figure out if $n$ is prime per se, but it gives us the value of $$ 2B_n(i) + I_n(i) = 2(n+2) = 2n+4. $$ Here is the case where $n=7$:
And here is the case where $n=6$:
I labelled the intersection points with the integer grid for visibility. So basically the only way that $\Delta_n(i)$ will have the same number of interior points when $i=1,\cdots,n-2$ is if it also has the same number of boundary points by Pick's theorem, since those triangles all have the same area and all have integer coordinate vertices.
But how is it possible that a line segment from $(0,0)$ to $(i,n-i)$ intersects points on the integer grid? This happens if there exists a rational number $\lambda \in ]0,1[$ such that $\lambda i$ and $\lambda(n-i)$ are both integers. Writing $\lambda = a/b$ with $a$ and $b$ coprime, this means in particular that $a<b$ and $b$ divides both $i$ and $n-i$. The existence of such a $b$ is necessary and sufficient to find an intersection point on the integer grid with the segment (we can just take $a=1$) and $b$ exists if and only if $\gcd(i,n-i) > 1$. But $\gcd(i,n-i) = \gcd(i,n)$, so basically each integer $i$ between $1$ and $n-1$ satisfying $g_n(i) \overset{def}= \gcd(i,n) > 1$ will have $g_n(i) - 1$ points of intersection with the integer grid (excluding $(i,n-i)$ and $(0,0)$), namely corresponding to the values of $\lambda$ equal to $\frac 1{g_n(i)}, \frac 2{g_n(i)}, \cdots, \frac{g_n(i)-1}{g_n(i)}$.
We now show that the number of interior points of $\Delta_n(i)$ for $i=1,\cdots,n-2$ are going to be the same if and only if $n$ is prime or $n=4$, because in the first case, $g_n(i) = 1$ for $i=1,\cdots,n-1$, and in the second case, $g_4(1)=1, g_4(2)=2$ and $g_4(3) = 1$, so $g_4(1)+g_4(2) = g_4(2) + g_4(3)$.
The number $n=4$ is the only number small enough not to be prime that works, because whenever $n > 4$ and $n$ has a prime divisor say $p > 2$, we have $g_n(1) = 1$ and $g_n(2) = 1$ or $2$, but $g_n(p) = p$ and $g_n(p+1) = 1$. If $n$ is a power of $2$ greater than $4$, we have $g_n(1) = 1$ and $g_n(2) = 2$ but $g_n(n/2) = n/2$ and $g_n(n/2+1) = 1$.
Hope that helps,