AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

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

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!

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