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.
