# “Overflow” in Extended Euclidean Algorithm

Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?).

I wonder if there is a proof that when evaluating extended Euclidean algorithm the Bézout's coefficients (that is s and t in identity as + bt = gcd(a, b)) will not exceed some reasonable values (depending on a, b, I guess). In particular implementation on some general-purpose programming language I'm interested in overflow correctness of the program.

To be precise I can mention that I use Victor Shoup's description of the algorithm (4.2 in his book “A Computational Introduction to Number Theory and Algebra” freely available from his homepage).

• I think this is definitely within scope. – Suresh Venkat Dec 1 '10 at 20:41

Lemma. For every integers $a,b \neq 0$, $\gcd(a,b) = ax + by$ for some integers $x,y$. Also, we may assume $|x| \leq |b|$ and $|y| \leq |a|$.
In general this is true in every Euclidean domain $R$ with a multiplicative Euclidean function $f$. In the case here when $R = \mathbf{Z}$, we have $f(x) = |x|$ which is multiplicative.
• Can this be generalized? say there exist a solution to $\gcd(a_1,\ldots,a_n) = \sum_{i} x_ia_i$ such that $\sum_{i}|x_i|\leq \sum_{i}|a_i|$? – Chao Xu Mar 24 '17 at 13:54