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

From ProofWiki
Jump to navigation Jump to search


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$.


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


\(\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.