4

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)?

Servaes
  • 63,261
  • 7
  • 75
  • 163
nik_97
  • 41

2 Answers2

4

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.

Servaes
  • 63,261
  • 7
  • 75
  • 163
  • "Then take an appropriate multiple of $x_0$ and $y_0$ to get as close to $c$ as possible, i.e. multiply both by $ (\frac{c}{\gcd(x,y)}) $ rounded to the nearest integer." Could you please explain this in more detail ? – nik_97 Jun 05 '16 at 14:02
  • @nik_97 There was a typo, fixed it now. – Servaes Jun 05 '16 at 14:10
  • Well, that line is still not clear to me :/ . – nik_97 Jun 06 '16 at 14:00
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)).$

Mutasim Mim
  • 600
  • I tried doing this for the equation $|10x-3y-4|$ .I got the answer as minimum =1,whereas the correct answer is 0 (for $x=1,y=2$) . In case you're familiar with C language, I used min = gcd(a,b)%c ; where gcd(a,b) is calculated recursively using Euclid's algorithm. – nik_97 Jun 05 '16 at 13:51
  • Sorry there was a typo that I fixed. The answer is $c $ $(\mod gcd(a,b))$. Now it clearly works for your example. – Mutasim Mim Jun 05 '16 at 14:33