AoPSWiki

Our Precalculus course starts on Dec. 4. Master trig, complex numbers, and vectors and matrices in 2 and 3 dimensions. Click here to enroll today!

Personal tools

Log in

Search

Toolbox

Bezout's Lemma

From AoPSWiki

Bezout's Lemma states that if $x$ and $y$ are nonzero integers and $g = \gcd(x,y)$ , then there exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=g$ . In other words, there exists a linear combination of $x$ and $y$ equal to $g$ .

Furthermore, $g$ is the smallest positive integer that can be expressed in this form, i.e. $g = \min\{x\alpha+y\beta|\alpha,\beta\in\mathbb Z, x\alpha+y\beta > 0\}$ .

In particular, if $x$ and $y$ are relatively prime then there are integers $\alpha$ and $\beta$ for which $x\alpha+y\beta=1$ .

Contents

1 Proof
2 Generalization to Principal Ideal Domains
3 Proof
4 See also

Proof

Let $x = gx_1$ , $y = gy_1$ , and notice that $\gcd(x_1,y_1) = 1$ .

Since $\gcd(x_1,y_1)=1$ , $\text{lcm}(x_1,y_1)=x_1y_1$ . So $\alpha=y_1$ is smallest positive $\alpha$ for which $x\alpha\equiv 0\pmod{y}$ . Now if for all integers $0\le a,b<y_1$ , we have that $x_1a\not\equiv x_1b\pmod{y_1}$ , then one of those $y_1$ integers must be 1 from the Pigeonhole Principle. Assume for contradiction that $x_1a\equiv x_1b\pmod{y_1}$ , and WLOG let $b>a$ . Then, $x_1(b-a)\equiv 0\pmod y_1$ , and so as we saw above this means $b-a\ge y_1$ but this is impossible since $0\le a,b<y_1$ . Thus there exists an $\alpha$ such that $x_1\alpha\equiv 1\pmod{y_1}$ .

Therefore $y_1|(x_1\alpha-1)$ , and so there exists an integer $\beta$ such that $x_1\alpha - 1 = y_1\beta$ , and so $x_1\alpha + y_1\beta = 1$ . Now multiplying through by $g$ gives, $gx_1\alpha + gy_1\alpha = g$ , or $x\alpha+y\beta = g$ .

Thus there does exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=g$ .

Now to prove $g$ is minimum, consider any positive integer $g' = x\alpha'+y\beta'$ . As $g|x,y$ we get $g|x\alpha'+y\beta' = g'$ , and as $g$ and $g'$ are both positive integers this gives $g\le g'$ . So $g$ is indeed the minimum.

Generalization to Principal Ideal Domains

Bezout's Lemma can be generalized to principal ideal domains.

Let $R$ be a principal ideal domain, and consider any $x,y\in R$ . Let $g = \gcd(x,y)$ . Then there exist elements $r_1,r_2\in R$ for which $xr_1+yr_2 = g$ . Furthermore, $g$ is the minimal such element (under divisibility), i.e. if $g' = xr_1'+yr_2'$ then $g|g'$ .

Note that this statement is indeed a generalization of the previous statement, as the ring of integers, $\mathbb Z$ is a principal ideal domain.

Proof

Consider the ideal $I = (x,y) = \{xr_1+yr_2|r_1,r_2\in R\}$ . As $R$ is a principal ideal domain, $I$ must be principle, that is it must be generated by a single element, say $I = (g)$ . Now from the definition of $I$ , there must exist $r_1,r_2\in R$ such that $g = xr_1+yr_2$ . We now claim that $g = \gcd(x,y)$ .

First we prove the following simple fact: if $z\in I$ , then $g|z$ . To see this, note that if $z\in I = (g)$ , then there must be some $r\in R$ such that $z = rg$ . But now by definition we have $g|z$ .

Now from this, as $x,y\in I$ , we get that $g|x,y$ . Furthermore, consider any $s\in R$ with $s|x,y$ . We clearly have that $s|xr_1+yr_2 = g$ . So indeed $g = \gcd(x,y)$ .

Now we shall prove minimality. Let $g' = xr_1'+yr_2'$ . Then as $g|x,y$ , we have $g|xr_1'+yr_2' = g'$ , as desired.

See also

This article is a stub. Help us out by expanding it.

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Bezout%27s_Lemma"

Categories: Number theory | Abstract algebra | Ring theory | Stubs

Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us