Shortest Possible Distance between Lattice Points on Straight Line in Cartesian Plane

Theorem

Let $\LL$ be the straight line defined by the equation:

$a x - b y = c$

Let $p_1$ and $p_2$ be lattice points on $\LL$.

Then the shortest possible distance $d$ between $p_1$ and $p_2$ is:

$d = \dfrac {\sqrt {a^2 + b^2} } {\gcd \set {a, b} }$

where $\gcd \set {a, b}$ denotes the greatest common divisor of $a$ and $b$.

Proof

Let $p_1 = \tuple {x_1, y_1}$ and $p_2 = \tuple {x_2, y_2}$ be on $\LL$.

Thus:

 $\ds a x_1 - b y_1$ $=$ $\ds c$ $\ds a x_2 - b y_2$ $=$ $\ds c$

From Solution of Linear Diophantine Equation, it is necessary and sufficient that:

$\gcd \set {a, b} \divides c$

for such lattice points to exist.

Also from Solution of Linear Diophantine Equation, all lattice points on $\LL$ are solutions to the equation:

$\forall k \in \Z: x = x_1 + \dfrac b m k, y = y_1 - \dfrac a m k$

where $m = \gcd \set {a, b}$.

So we have:

 $\ds x_2$ $=$ $\ds x_1 + \dfrac b m k$ $\ds y_2$ $=$ $\ds y_1 - \dfrac a m k$

for some $k \in \Z$ such that $k \ne 0$.

The distance $d$ between $p_1$ and $p_2$ is given by the Distance Formula:

 $\ds d$ $=$ $\ds \sqrt {\paren {x_1 - \paren {x_1 + \dfrac b m k} }^2 + \paren {y_1 - \paren {y_1 - \dfrac a m k} }^2}$ $\ds$ $=$ $\ds \sqrt {\paren {\dfrac {b k} m}^2 + \paren {\dfrac {a k} m}^2}$ $\ds$ $=$ $\ds \sqrt {\dfrac {k^2 \paren {a^2 + b^2} } {m^2} }$ $\ds$ $=$ $\ds k \dfrac {\sqrt {a^2 + b^2} } m$

This is a minimum when $k = 1$.

Hence the result.

$\blacksquare$