Facts About Visible Points




(For reference, see "Some Number Theory Notes" on our homepage.)




Definition: The fundamental lattice $\QTR{cal}{L}$ consists of all those points in the plane with integer coordinates. These points are called lattice points.

For example, $(2,3)$ and $(-7,14)$ are points in $\QTR{cal}{L}$, while $(1,4/5)$ does not lie in $\QTR{cal}{L}$.




Suppose that a tree is growing at each point in $\QTR{cal}{L}$. These trees are infinitely thin, but opaque. Imagine that we are standing at the origin and we look toward the tree at $(6,8)$. Can we see it? The answer is no, because our line of sight from $\left( 0,0\right) $ to $(6,8)$ passes through the nearer point $(3,4)$, and the opaque tree there obscures it. On the other hand, we can see the tree at $(3,4)$ because it's the closest lattice point on this line to the origin. This inspires the following definitions.




Definition: The line to point $P$ means the line from the origin to point $P$.

Definition: A point $P$ in the lattice $L$ is called visible if the line to $P$ contains no lattice point closer to the origin than $P$.




Remark: In giving the mathematical definition of "visible" we have dispensed with the "tree" metaphor, since it was just used as motivation. It is also easier to say "a point $P$ is visible" than to say "the tree at point $P$ is visible."

It is not too difficult to determine, using number theory, exactly which points are visible. This is done in the exercises. We will use the following facts from number theory:




Very Important Theorem: If $d=\gcd (a,b)$ then there are integers $x$ and $y$ such that $d=xa+yb$.




(This Theorem is proved using the Euclidean algorithm to find $x$ and $y$. See "GCDs" on the website.)

We sometimes express this by saying that "The greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b.$


Here is a very useful consequence of this theorem:

Proposition: If $a\ |\ b\cdot c$ and $\gcd (a,b)=1$, then $a\ |\ c$.

Proof: Since $1=\gcd (a,b)$, we can write MATH (because of the Very Important Theorem). Multiply through by $c$: MATH. Since $a$ divides everything on the right-hand side, it must divide $c$. $\blacksquare $




Here, then, is the answer about Visibles:




Theorem: $(m,n)$ is visible if and only if $\gcd (m,n)=1$.




Proof: There are two things to prove since this and an "if and only if" statement: we must show that if $(m,n)$ is visible, then MATH, and we must show that if $\gcd (m,n)=1$ then $(m,n)$ is visible.

OK, so suppose $(m,n)$ is visible, and let $d=\gcd (m,n)$. The $m/d$ and $n/d $ are whole numbers --- since $d$ goes evenly into $a$ and $b$. (NOTE: Don't confuse the division $A/B$ with the statement $A\ |\ B$, which says " $A$ divides $B$." ). Note that $(m,n)$ and MATH lie on the same line through the origin. But the point $(m/d,n/d)$ is closer to the origin than $(m,n)$ unless $d=1$. Since $(m,n)$ is supposed to be visible, there can't be any point on its line closer to the origin, so we must have $d=1$. This finishes the (easier) first half.

Now let's suppose $\gcd (m,n)=1$. We will show that $(m,n)$ is visible by showing that any other point on its line through the origin is further away. Suppose $(a,b)$ also lies on this line. Then MATH. Cross multiplying, we have $mb=an$. Since $\gcd (m,n)=1$, we must have $m\ |\ a$, so $a=km$. Substituting, we have: $mb=an=(km)n$, so $b=kn$. Therefore $(a,b)=(km,kn)$, so unless $k=1$, the point $(a,b)$ lies further from the origin than $(m,n)$. Thus, $(m,n)$ is visible.

This completes the proof, which we indicate by the symbol: $\blacksquare $