“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).
This is called the Bézout's identity/lemma (not to be confused with Bézout's theorem in algebraic geometry), which states:


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


Proofs can be founded in standard algebra textbooks. Also you can prove it yourself by induction on the iterations of gcd process.

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.