Suppose we have coprime integers $(a,b)$ and let $\ell \in \mathbb{Z}$ be arbitrary. The general solution to the linear Diophantine equation $ax+by=\ell$ is given by $x=\ell x' + bt$ and $y=\ell y' – at$ where $x', y'$ satisfy $ax'+by'=1$ and are found by the extended Euclidean algorithm, and $t$ ranges over $\mathbb{Z}$.
I'm interested in minimal solutions to the equation, in the sense of the $L^{\infty}$ norm. That is to say, we're looking for solutions $(x,y)$ to the equation which minimize $\text{max}(|x|, |y|)$.
If $\ell=1$, then the minimal solution to $ax+by=1$ is exactly $(x', y')$, where $(x', y')$ are defined as above, and it satisfies $|x'| \leq |b|$ and $|y'|\leq |a|$. This is just because the extended Euclidean algorithm always produces minimal solutions. If $\ell \neq 1$, then we might think that $(\ell x', \ell y')$ are the minimal solutions, but this is not correct. A simple example is $7x+3y=10$. The optimal solution here is of course $(x,y)=(1,1)$. This is better than any solution of the form $(10x', 10y')$, where $(x',y')$ are minimal solutions to $7x+3y=1$.
Is there, in general, a decent algorithm for the minimal solution? Alternatively, is there a (decent) estimate for the minimal solution? For coprime $(a,b)$, if we define a function $f_{(a,b)}(n)$ given by $$f_{(a,b)}(n) = \min_{\{(x,y) \in \mathbb{Z}^2 : ax+by=n\}} \max (|x|, |y|)$$ is there anything that can be said to how $f$ behaves as $n \to \infty$? Certainly, $f$ would tend to $\infty$, but are there precise asymptotic estimates or concrete inequalities? If I had to guess, I would reckon that it would be $O(n)$.
Note that, in more general terms, we can ask this question for any nonempty set $S$ of coprime integers, and linear Diophantine equations with coefficients in $S$. Here, we've restricted ourselves to the case where $|S| = 2$. A general solution would also be great.
Best Answer
Suppose $\,(x',y')\,$ is the minimal solution to the $\,ax+by=1\,$ generated by the extended Euclidean algorithm. Then as you pointed out, $\,(nx',ny')\,$ will be a solution to $\,ax+by=n\,$ but not necessarily minimal. However, note that $\,(nx'-kb,ny'+ka)\,$ will also be a solution for any $\,k \in \Bbb Z.\,$
To find the minimal solution to $\,ax+by=n\,$, we simply need to find $\,k\,$ such that $\,nx'-kb\,$ and $\,ny'+ka\,$ are as close as possible [see note below]. To do that, we solve the equation $\,nx'-kb=ny'+ka\,$ for $\,k\,$; if the equation yields an integral $\,k\,$, then we will have our minimal solution, otherwise either $\,\lfloor k \rfloor\,$ or $\,\lceil k \rceil\,$ (whichever is closer to $\,k\,$) will generate the minimal solution.
In your particular example, the extended Euclidean algorithm should generate the solution $\,(1,-2)\,$ as the minimal solution to $\,7x+3y=1,\,$ so our starting solution to $\,7x+3y=10,\,$ would be $\,(10,-20).\,$ Then solving the equation $\,10-3k=-20+7k\,$ gives $\,k=3\,$ which yields the minimal solution $\,(1,1).\,$
[Note: this assumes that $\,ab \gt 0;\,$ if not then one can just solve $\,ax-by=n\,$ and then use the solution $\,(nx'-kb,-[ny'+ka]).\,$]