Given two numbers $a, b \in \mathbb{Z}$ with $gcd(a, b) = 1$, the set $P = \{(k \cdot a, k \cdot b) \; | \; k \in \mathbb{Z}\}$ is the intersection of points on the line $g: ax = by$ and the integer points $I = \{(x, y) \; | \; x,y \in \mathbb{Z}\}$ in the plane.
We know that there is an infinite number of lines parallel to $g$, that also contain an individual infinite subset of integer points $I$.
(How) can we analytically determine the integer point subsets of the two lines, that are closest to $g$?
For clarification, see this figure for $a = -2$ and $b = 3$. $g$ is the blue line, $P$ is the set of blue dots. We are looking for the set of red and green dots.
You may notice that this is actually a very abstract problem of discrete mathematics, put into a geometric application.
For those interested: I came up with this problem while trying to solve this quiz on codewars.com.
Best Answer
A line parallel to $\ g\ $ must be of the form $\ ax-by=c\ $, in which case its distance from $\ g\ $ is $\ \frac{|c|}{\sqrt{a^2+b^2}}\ $. If it contains any integer points, then $\ c\ $ must be an integer. Since the lines $\ c_1: ax-by=1\ $ and $\ c_{-1}:ax-by=-1\ $ both contain an infinite number of integer points, they must be the lines closest to $\ g\ $ that do so. You can use the extended Euclidean algorithm to find an integer point $\ \left(x_0,y_0\right)\ $ on $\ c_1\ $ (i.e. such that $\ ax_0-by_0=1\ $). The set of integer points on $\ c_1\ $ is then $$ \left\{\left(x_0+kb, y_0+ka\right)\big|\,k\in\mathbb{Z}\right\}\ , $$ and the set of integer points on $\ c_{-1}\ $ is $$ \left\{\left(-x_0+kb, -y_0+ka\right)\big|\,k\in\mathbb{Z}\right\}\ . $$