Estimates for Bezout coefficients 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?
 A: 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.
A: I won't quite satisfy Denis Osin's request, but indicate the main idea to bound
the sum of the absolute value of the x's, given that k is the sum of the given
positive a's, and that a dot x = 1 (leaving the case gcd > 1 to Denis).
So pick a coefficient that is large in absolute value (assume it is x_i associated with a_i)
, and then find a different large x_j with opposite sign belonging to a_j .  Then
x_j can be reduced by a_i and x_i  enhanced by a_j, without changing the sum of 1,
but possibly minimizing the sum of the absolute value of the x's, unless 2(abs(x_i)
+ abs(x_j)) =< a_i + a_j .  So I think we can get the abs(x)'s down to k/2 or lower.
One can ask questions like "what if there is only one large x, and it belongs to the
biggest a_i?"  I would respond that there is something wierd going on,  but that if the sum
of the abs(x)'s also exceeds the sum of the a's, then there must be a lot of x's opposite in
sign to the large x, and that they can share the burden of adjustment among themselves.
After I recover from dental surgery, I will try firming this up if no one else has.
Gerhard "Medication Making Mathematics More Mellow" Paseman, 2012.10.02
