Minimum of $|ax-by+c|$

Question

Find the minimum of the function

$$ f(x,y)=|ax-by+c|$$

where $a,b,c \in \mathbb N$ and $x,y \in \mathbb Z$.

The questions here and here are similar but they are in cases where $x, y$ are bounded.Taking the partial derivatives,etc. doesn't help. Is there a way to do this efficiently(for a computer program)?

Answer 1

The smallest positive value that $ax-by$ takes is $\gcd(a,b)$. Finding $x_0$ and $y_0$ for which $ax-by$ is minimal can be done with Euclid's algorithm. Then take an appropriate multiple of $x_0$ and $y_0$ to get as close to $c$ as possible, i.e. multiply both by $\tfrac{c}{\gcd(a,b)}$ rounded to the nearest integer.

Answer 2

Let $(a,b)=d$. Note that for all $k\in \mathbb Z$, there are $x,y\in \mathbb Z$ such that $ax-by=kd$. Also, for all $x,y\in \mathbb Z$, $ax-by$ is of the form $kd$, for some $k\in \mathbb Z$. So the minimum value of $|ax-by+c|$ is the same as the minimum value of the numbers of the form $|kd+c|$. It is obvious that this minimum value is $c$ $(\mod gcd(a,b)).$