Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 1

up vote 1 down vote accepted

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$. plot for f(k)

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.