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

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

 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 .
Tags: number theory.