# Small $$L_1$$ norm solution to a linear Diophantine equation

Let $$a=(a_1,\ldots,a_n)$$ be $$n$$ integers with $$\gcd(a_1,\ldots,a_n)=1$$. There exists a integral vector $$x=(x_1,\ldots,x_n)$$, such that $$\sum_{i=1}^n x_ia_i = 1$$. How large is the solution $$x$$? By Bézout's lemma, when $$n=2$$, we can obtain that $$\|x\|\leq \|a\|$$. Here $$\|\cdot \|$$ is the $$L_1$$ norm.

However, I could not find a general bound of $$\|x\|$$ anywhere. Here we prove that the bound on $$\|x\|$$ is true in general. Before that, we first introduce a lemma from [1].

Lemma1

Let $$a=(a_1,\ldots,a_n)$$ be a vector of positive integers with at least $$2$$ elements, it does not contain $$1$$ and $$\gcd(a)=1$$. If $$g_k = \gcd(a_k,\ldots,a_n)$$, then there exist a solution to $\sum_{i=1}^n x_i a_i = 1$ such that for all $$1\leq i\leq n-1$$, $|x_i|\leq \frac{g_{i+1}}{2g_i}$ and $$|x_n|\leq \frac{\max(a_1,\ldots,a_{n-1})}{2}$$.

Theorem2

Let $$a$$ be a vector of positive integers such that $$\gcd(a)=1$$, then there exists a integral solution to $$x \cdot a=1$$ such that $$\|x\|\leq \frac{1}{2}(\min(a)+\max(a))$$.

Proof

Let $$a=(a_1,\ldots,a_n)$$. Let $$a_n=\min(a)$$. We can assume $$1$$ is not in $$a$$, otherwise we can find $$x$$ such that $$\|x\|=1$$. Let $$g_i = \gcd(a_i,\ldots,a_n)$$. Hence $$g_n = \min(a)$$. We consider a solution to $$\sum_{i=1}^n x_ia_i = 1$$ satisfies Lemma 1. Let $$I = \set{i | g_{i+1}\geq 2g_{i}, i\leq n-1}$$ and $$j=\min(I)$$. One can algebraically check that $$a/b\leq a-b$$ holds if both $$a\geq 2b$$ and $$b\geq 2$$. In particular, we have $$\frac{g_{i+1}}{g_i} \leq g_{i+1}-g_i$$ for all $$i\in I\setminus \set{j}$$. $\sum_{i\in I} |x_i| \leq \frac{1}{2} \sum_{i\in I} \frac{g_{i+1}}{g_i} \leq \frac{g_{j+1}}{2} + \frac{1}{2} \sum_{i\in I, i\neq j} g_{i+1} - g_i \leq \frac{g_{j+1}}{2} + \frac{1}{2} \sum_{i=j+1}^{n-1} g_{i+1}-g_i = \frac{1}{2}g_n = \frac{\min(a)}{2}.$

$\|x\| = \sum_{i=1}^n |x_i| = |x_n| + \sum_{i\in I} |x_i| \leq \frac{\min(a)+\max(a)}{2}$

Corollary3

Let $$a$$ be a vector of integers such that $$\gcd(a)=1$$, then there exists a integral solution to $$x \cdot a=1$$ such that $$\|x\|\leq \|a\|$$.

# References

[1] D. Ford, G. Havas, A new algorithm and refined bounds for extended gcd computation, in: H. Cohen (Ed.), Algorithmic Number Theory: Second International Symposium, Ants-Ii Talence, France, May 18–23, 1996 Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 1996: pp. 145–150 10.1007/3-540-61581-4_50.

Posted by Chao Xu on 2017-08-26.
Tags: number theory.