<p>This is called the <a href="http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity" rel="nofollow">Bézout's identity/lemma</a> (not to be confused with <a href="http://en.wikipedia.org/wiki/B%C3%A9zout%27s_theorem" rel="nofollow">Bézout's theorem</a> in algebraic geometry), which states:</p>

<blockquote>
  <p><strong>Lemma.</strong> 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|$.</p>
</blockquote>

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

<p>In general this is true in every <a href="http://en.wikipedia.org/wiki/Euclidean_domain" rel="nofollow">Euclidean domain</a> $R$ with a multiplicative Euclidean function $f$. In the case here when $R = \mathbf{Z}$, we have $f(x) = |x|$ which is multiplicative.</p>

CC BY-SA 3.0
2017-03-24T13:54:31.373Z
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
CC BY-SA 2.5
2010-12-02T07:52:24.180Z
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.
Artem Pelenitsyn
CC BY-SA 2.5
2010-12-02T07:56:50.113Z
Try Theorem 2.5 in the book by Keijo Ruohonen, http://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. http://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T03:15:52.990Z
2010-12-02T06:23:25.600Z
2010-12-02T06:23:25.600Z
Hsien-Chih Chang 張顯之
<p>Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?).</p>

<p>I wonder if there is a proof that when evaluating extended Euclidean algorithm the Bézout's coefficients (that is <em>s</em> and <em>t</em> in identity <em>as</em> + <em>bt</em> = gcd(<em>a</em>, <em>b</em>)) 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.</p>

<p>To be precise I can mention that I use Victor Shoup's description of the algorithm (4.2 in his book “<a href="http://shoup.net/ntb/" rel="nofollow">A Computational Introduction to  Number Theory and Algebra</a>” freely available from his homepage).</p>

CC BY-SA 2.5
2010-12-01T20:41:04.320Z
I think this is definitely within scope.
Suresh Venkat
<ds.algorithms><nt.number-theory>
“Overflow” in Extended Euclidean Algorithm
Artem Pelenitsyn
# “Overflow” in Extended Euclidean Algorithm

(Asked by: username_0 on 2010-12-01)

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](http://shoup.net/ntb/)” freely available from his homepage).

**Tags:** ds.algorithms, nt.number-theory
> **Comments:**
> **username_1**: I think this is definitely within scope.  

---

## 1 answers

### Answer by username_2 on 2010-12-02. Score: 13 | Accepted answer

This is called the [Bézout's identity/lemma](http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity) (not to be confused with [Bézout's theorem](http://en.wikipedia.org/wiki/B%C3%A9zout%27s_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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Try Theorem 2.5 in the book by Keijo Ruohonen, http://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. http://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907  
> **username_3**: 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|$?  

---

