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

From ProofWiki
Jump to navigation Jump to search

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


This article, or a section of it, needs explaining.
In particular: Review the above -- it is not given that $a$ and $b$ are integers.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.



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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Shortest_Possible_Distance_between_Lattice_Points_on_Straight_Line_in_Cartesian_Plane&oldid=591242"