# Small $L_{1}$ norm solution to a linear Diophantine equation

Let $a=(a_{1},…,a_{n})$ be $n$ integers with $g(a_{1},…,a_{n})=1$. There exists a integral vector $x=(x_{1},…,x_{n})$, such that $∑_{i=1}x_{i}a_{i}=1$. How large is the solution $x$? By Bézout’s lemma, when $n=2$, we can obtain that $∥x∥≤∥a∥$. Here $∥⋅∥$ 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].

Let $a=(a_{1},…,a_{n})$ be a vector of positive integers with at least $2$ elements, it does not contain $1$ and $g(a)=1$. If $g_{k}=g(a_{k},…,a_{n})$, then there exist a solution to $i=1∑n x_{i}a_{i}=1$ such that for all $1≤i≤n−1$, $∣x_{i}∣≤2g_{i}g_{i+1} $ and $∣x_{n}∣≤2max(a_{1},…,a_{n−1}) $.

Let $a$ be a vector of positive integers such that $g(a)=1$, then there exists a integral solution to $x⋅a=1$ such that $∥x∥≤21 (min(a)+max(a))$.

Let $a=(a_{1},…,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}=g(a_{i},…,a_{n})$. Hence $g_{n}=min(a)$. We consider a solution to $∑_{i=1}x_{i}a_{i}=1$ satisfies Lemma 1. Let $I={i∣g_{i+1}≥2g_{i},i≤n−1}$ and $j=min(I)$. One can algebraically check that $a/b≤a−b$ holds if both $a≥2b$ and $b≥2$. In particular, we have $g_{i}g_{i+1} ≤g_{i+1}−g_{i}$ for all $i∈I∖{j}$. $i∈I∑ ∣x_{i}∣≤21 i∈I∑ g_{i}g_{i+1} ≤2g_{j+1} +21 i∈I,i=j∑ g_{i+1}−g_{i}≤2g_{j+1} +21 i=j+1∑n−1 g_{i+1}−g_{i}=21 g_{n}=2min(a) .$

$∥x∥=i=1∑n ∣x_{i}∣=∣x_{n}∣+i∈I∑ ∣x_{i}∣≤2min(a)+max(a) $

Let $a$ be a vector of integers such that $g(a)=1$, then there exists a integral solution to $x⋅a=1$ such that $∥x∥≤∥a∥$.