Small norm solution to a linear Diophantine equation
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 [1].
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 .