11
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ You reference Wikipedia, but there is no such words: “Also, we may assume...”. Would you please name some “standard algebra textbook”? I looked into Rotman's First course in abstract algebra: there is description of Eucl. Algo, but there is no such bounds on coefficients. Same story in Shoup's book, which was referenced by me in my post. $\endgroup$ – Artem Pelenitsyn Dec 2 '10 at 7:52
  • 2
    $\begingroup$ Try Theorem 2.5 in the book by Keijo Ruohonen, math.tut.fi/~ruohonen/MC.pdf. If my momery is correct, the book by Fraleign has the lemma in the main text or in the exercises. amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907 $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 7:56
  • 1
    $\begingroup$ 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|$? $\endgroup$ – Chao Xu Mar 24 '17 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.