Difference between revisions of "Bézout's Identity"

Latest revision as of 01:41, 1 September 2024

Bézout's Identity 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$ .

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_1\alpha\equiv 0\pmod{y_1}$ . Now if for all distinct $a,b \in\mathbb{Z}$ satisfying $0\le a,b<y_1$ we have $x_1a\not\equiv x_1b\pmod{y_1}$ , then, by the Pigeonhole Principle, we can express every residue of $y_1$ as a multiple of $x_1$ . In particular, there is some positive $\alpha<y_1$ for which $x_1\alpha\equiv 1\pmod{y_1}$ . 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\beta = 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/Extension of Bézout's Identity

Let $a_1, a_2,..., a_m$ be positive integers. Then there exists integers $x_1, x_2, ..., x_m$ such that $\sum_{i=1}^{m} a_ix_i = \gcd(a_1, a_2, ..., a_m)$ Also, $\gcd(a_1, a_2, ..., a_m)$ is the least positive integer satisfying this property.

Proof

Consider the set $P = \{n \in \mathbb{Z}^{+}|n= \sum_{i=1}^{m} a_iu_i: u_1, \dots, u_m \in \mathbb{Z}\}$ . Obviously, $P \neq \emptyset$ . Thus, because all the elements of $P$ are positive, by the Well Ordering Principle, there exists a minimal element $d \in P$ . So

$d=a_1x_1 +a_2x_2 + \dots +a_mx_m$

if $n >d$ and $n \in S$ then $n=a_1u_1 +a_2u_2 + \dots +a_mu_m$ But by the Division Algorithm:

$n=qd +r \Longrightarrow r=n-qd$ $= \sum_{i=1}^m a_i(u_i-qx_i)$ $\Longrightarrow r\in P$

But $0 \le r<d$ so this would imply that $r \in P$ which contradicts the assumption that $d$ is the minimal element in $P$ . Thus, $r=0$ hence, $d|n$ . But this would imply that $d|a_i$ for $i \in \{1, 2,\dots,m\}$ because $a_i = a_i \cdot1 + \sum_{k=1; k \neq i}^{m}(a_k\cdot0) \Longrightarrow \{a_1, a_2, \dots, a_m \} \subset P$ . Now, because $d|a_i$ for $i \in \{1, 2,\dots,m\}$ we have that $d|\gcd(a_1, a_2,\dots, a_m)|a_i$ . But then we also have that $\gcd(a_1, a_2,\dots, a_m)|\sum_{i=1}^m a_iu_i =d$ . Thus, we have that $\boxed{d=\gcd(a_1, a_2,\dots, a_m)}$ $\Box$

@@ Line 7: / Line 7: @@
 Let <math>x = gx_1</math>, <math>y = gy_1</math>, and notice that <math>\gcd(x_1,y_1) = 1</math>.
-Since <math>\gcd(x_1,y_1)=1</math>, <math>\text{lcm}(x_1,y_1)=x_1y_1</math>. So <math>\alpha=y_1</math> is smallest positive <math>\alpha</math> for which <math>x_1\alpha\equiv 0\pmod{y}</math>. Now if for all integers <math>0\le a,b<y_1</math>, we have that <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then one of those <math>y_1</math> integers must be 1 from the [[Pigeonhole Principle]]. Assume for contradiction that <math>x_1a\equiv x_1b\pmod{y_1}</math>, and WLOG let <math>b>a</math>. Then, <math>x_1(b-a)\equiv 0\pmod {y_1}</math>, and so as we saw above this means <math>b-a\ge y_1</math> but this is impossible since <math>0\le a,b<y_1</math>. Thus there exists an <math>\alpha</math> such that <math>x_1\alpha\equiv 1\pmod{y_1}</math>.
+Since <math>\gcd(x_1,y_1)=1</math>, <math>\text{lcm}(x_1,y_1)=x_1y_1</math>. So <math>\alpha=y_1</math> is smallest positive <math>\alpha</math> for which <math>x_1\alpha\equiv 0\pmod{y_1}</math>. Now if for all distinct <math>a,b \in\mathbb{Z}</math> satisfying <math>0\le a,b<y_1</math> we have <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then, by the [[Pigeonhole Principle]], we can express every residue of <math>y_1</math> as a multiple of <math>x_1</math>. In particular, there is some positive  <math>\alpha<y_1</math> for which <math>x_1\alpha\equiv 1\pmod{y_1}</math>. Assume for contradiction that <math>x_1a\equiv x_1b\pmod{y_1}</math>, and WLOG let <math>b>a</math>. Then, <math>x_1(b-a)\equiv 0\pmod {y_1}</math>, and so as we saw above this means <math>b-a\ge y_1</math> but this is impossible since <math>0\le a,b<y_1</math>. Thus there exists an <math>\alpha</math> such that <math>x_1\alpha\equiv 1\pmod{y_1}</math>.
 Therefore <math>y_1|(x_1\alpha-1)</math>, and so there exists an integer <math>\beta</math> such that <math>x_1\alpha - 1 = y_1\beta</math>, and so <math>x_1\alpha + y_1\beta = 1</math>. Now multiplying through by <math>g</math> gives, <math>gx_1\alpha + gy_1\beta = g</math>, or <math>x\alpha+y\beta = g</math>.

Page

Toolbox

Search

Difference between revisions of "Bézout's Identity"

Latest revision as of 01:41, 1 September 2024

Contents

Proof

Generalization/Extension of Bézout's Identity

Proof

See also