The answer to my question is probably well-known, but I was unable to find a reference. 


The Bezout's identity states that for any positive non-zero integers $a\_1, \ldots , a\_n$ there exist integers $x\_1, \ldots , x\_n$ such that 
$$
a\_1x\_1+ \cdots + a\_nx\_n=gcd(a\_1, \ldots, a\_n) .
$$
What is the best estimate for $|x\_1|+\cdots + |x\_n|$ in terms of $|a\_1|+\cdots +|a\_n|$? 


More precisely, we define 
$$
b(a\_1, \ldots , a\_n) =\min\limits\_{a\_1x\_1+ \cdots + a\_nx\_n=gcd(a\_1, \ldots, a\_n)} (|x\_1|+\cdots + |x\_n|) 
$$
and 
$$
f(k)= \max\limits\_{|a\_1|+\cdots +|a\_n|\le k} b(a\_1, \ldots, a\_n) .
$$
What is known about the growth of $f(k)$?


Here is a very particular question. It is not hard to show that $f(k)=O(k^2)$. Is there any better estimate? Does $f(k)=O(k\log k)$ hold?



Estimates for Bezout coefficients
We can prove $b(a\_1,\ldots,a\_n) \leq a\_1+\cdots+a\_n$ (and thus $f(k) \leq k$) by elementary means as follows.


We may assume $\operatorname{gcd}(a\_1,\ldots,a\_n)=1$ and $1 < a\_1< \cdots <a\_n$.


Start with any Bézout identity $x\_1 a\_1+ \cdots + x\_n a\_n = 1$. Using the transformations $x\_n \leftarrow x\_n + ka\_1, x\_1 \leftarrow x\_1-ka\_n$, we may ensure $|x\_n| \leq a\_1$.


Similarly, we ensure $|x\_{n-1}| \leq a\_1$, but we choose the sign of $x\_{n-1}$ so that $x\_{n-1} a\_{n-1}$ and $x\_n a\_n$ have opposite signs. In this way $|x\_{n-1}a\_{n-1}+x\_n a\_n| \leq \max(|x\_{n-1} a\_{n-1}|,|x\_n a\_n|) \leq a\_1 a\_n$.


Repeating the process, for each $n-2 \geq k \geq 2$, we change $x\_k$ so that $|x\_k| \leq a\_1$ and $x\_k a\_k$ and $\sum\_{j=k+1}^n x\_j a\_j$ have opposite signs. Thus $|\sum\_{j=k}^n x\_j a\_j| \leq \max(|x\_k a\_k|,|\sum\_{j=k+1}^n x\_j a\_j|) \leq a\_1 a\_n$.


At the end we have $|x\_1 a\_1| \leq 1+ |\sum\_{j=2}^n x\_j a\_j| \leq 1+a\_1 a\_n<a\_1(1+a\_n)$ so $|x\_1| \leq a\_n$ and finally $|x\_1|+\cdots+|x\_n| \leq a\_n+(n-1)a\_1 \leq a\_1+\cdots+a\_n$.


I suspect that there are better bounds when $n$ is big.


