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?
Best Answer
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.