# Finding two integers with a given constraints

For a given positive integers $a,b$ and non negative integer $d$ find integers $x,y$ such that $ax+by=d$. There are many possible answers so another conditions are that:

1. $|x|+|y|$ is minimal
2. $a|x| + b|y|$ is minimal (in case of draw in 1.)

For example for: $a=648, b=375, d=4002$ we have $|x|=49, |y|=74$.

At the beginning this problem was about balance, but it comes to this.

One can see the similarity to the extended Euclidean algorithm but I don't know if it can be useful.

Of course there is a simple way to do this by starting with $x=0$ step $1$, and then we have corresponding $y$ to fixed $x$, and after some steps we have candidate for optimal pair $x,y$. The same must be computed starting from $y$. But it's irrelevant - this way is too slow. How can I solve this problem elegantly in nice time complexity? Can anyone help? I would be very grateful.

-
With $d:=0$, $\Longrightarrow ax + by=0 \Longrightarrow (x,y) = (0,0)$. So you might as well rephrase the question with "given positive integers $a,b,d$" – Rustyn Mar 21 '13 at 20:00

## 1 Answer

Note that if there are some solutions, then $D=\operatorname{gcd}(a,b)$ divides $d$, i.e. there is a $c\in\Bbb Z$ such that $d=cD$. Thus solving $xa+yb=d$ is equivalent to solve $xa'+yb'=c$, where $a'=\frac aD$ and $b'= \frac bD$. Therefore in the following we will suppose that $\operatorname{gcd}(a,b)=1$.

Claim: Every solution to $xa+yb=c$ is of the form $(cx_0+kb,cy_0-ka)$, where $k\in \Bbb Z$ and $(x_0,y_0)$ is such that $x_0a+y_0b=1=\operatorname{gcd}(a,b)$.

Proof: Note that $c=c\cdot1=c(x_0a+y_0b)=(cx_0)a+(cy_0)b$, so $(cx_0,cy_0)$ is indeed a solution. Moreover, if $(\bar{x},\bar{y})$ is a solution, then $$(\bar{x}+kb)a+(\bar{y}-ka)b=\bar{x}a+kab+\bar{y}b-kab=\bar{x}a+\bar{y}b=c$$ so that $(\bar{x}+kb,\bar{y}-ka)$ is a solution, too. Finally, if $(x,y),(x',y')$ are two solutions, then $$0=(xa+yb)-(x'a+y'b)=(x-x')a+(y-y')b$$ hence $a\mid(y-y')$ since $a,b$ are coprime, and $x-x'=\frac{y'-y}{a}b$.$\quad\square$

Now that we know the form of all possible solutions, we can solve your actual problem. First of all, let's find a solution $(x_0,y_0)$ to $xa+yb=1$ by Euclidean algorithm. Then let $$\left|cx_0+kb\right|+\left|cy_0-ka\right|=g(k)+h(k)=f(k):\Bbb R \to \Bbb R_{>0}$$ which is continuous and admits a global minimum. If, e.g., $b>a$, you can see that $\bar{k}$ such that $g(\bar{k})=0$ will realise such minimum. You can then check the (at most) two nearest integers to $\bar{k}$ for the minimum of $\left.f\right|_{\Bbb Z}$. I'm not sure if there is a way to determine directly which of them is the one you're looking for.

In case of draw proceed similarly with $f'(k)=\left|acx_0+kab\right|+\left|bcy_0-kab\right|$.

Here is an analysis for your example with $a'=648,b'=375,d=4002$, i.e. $a=216,b=125,c=1334$, since $\operatorname{gcd}(a',b')=3$.

Then $(x_0,y_0)=(11,-19)$, and since $a>b$ the minimum for $f(k)$ will be at $\bar{k}=\frac{cy_0}{a}\simeq -117.34$. In particular, the minimum for $\left.f\right|_{\Bbb Z}$ is at $k=-117$, where $cx_0+kb=49$ and $cy_0-ka=-74$.

-