The Art Gallery Guardian

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].

Lemma1

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 .

Theorem2

Let be a vector of positive integers such that , then there exists a integral solution to such that .

Proof

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 .

Corollary3

Let be a vector of integers such that , then there exists a integral solution to such that .

References

[1]
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.
Posted by Chao Xu on .
Tags: number theory.