# How can we find the minimal solutions to a linear Diophantine equation?

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.

• You might find some information by searching for "minimal element of a lattice". Commented Nov 22, 2019 at 5:03

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]).\,$$]
You can solve this problem via integer linear programming as follows. Let decision variable $$z$$ represent $$\max(|x|,|y|)$$, to be linearized. The problem is to minimize $$z$$ subject to: \begin{align} ax+by&=n\\ z&\ge x\\ z&\ge -x\\ z&\ge y\\ z&\ge -y\\ x,y,z&\in\mathbb{Z} \end{align}