Let be integers with . There exists a integral vector , such that . How large is the solution ? By Bézout’s lemma, when , we can obtain that . Here is the norm.
However, I could not find a general bound of anywhere. Here we prove that the bound on is true in general. Before that, we first introduce a lemma from .
Let be a vector of positive integers with at least elements, it does not contain and . If , then there exist a solution to such that for all , and .
Let be a vector of positive integers such that , then there exists a integral solution to such that .
Let . Let . We can assume is not in , otherwise we can find such that . Let . Hence . We consider a solution to satisfies Lemma 1. Let and . One can algebraically check that holds if both and . In particular, we have for all .
Let be a vector of integers such that , then there exists a integral solution to such that .
 D. Ford, G. Havas, A new algorithm and refined bounds for extended gcd computation, in: H. Cohen (Ed.), Algorithmic Number Theory: Second International Symposium, Ants-Ii Talence, France, May 18–23, 1996 Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 1996: pp. 145–150 10.1007/3-540-61581-4_50.