4 edited tags
3 added 141 characters in body; edited body

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?

2 edited body; added 18 characters in body

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 $g(k)$?f(k)\$?

1