1.8: Bezout's Lemma

Last updated
Save as PDF

Page ID: 82290

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Lemma \(\PageIndex{1}\): Bezout's Lemma

For all integers \(a\) and \(b\) there exist integers \(s\) and \(t\) such that \[\gcd(a,b)=sa+tb.\nonumber\]

Proof

If \(a=b=0\) then \(s\) and \(t\) may be anything since \[\gcd(0,0)=0=s\cdot0+t\cdot0.\nonumber\] So we may assume that \(a\ne 0\) or \(b\ne 0\). Let \[J=\{na+mb:n,m\in\mathbb{Z}\}.\nonumber\] Note that \(J\) contains \(a\), \(-a\), \(b\) and \(-b\) since \[\begin{aligned} a &=1\cdot a+0 \cdot b \\ -a &=(-1)\cdot a+0 \cdot b \\ b &=0 \cdot a+1 \cdot b \\ -b &=0 \cdot a+(-1) \cdot b.\end{aligned}\] Since \(a\ne 0\) or \(b\ne 0\) one of the elements \(a\), \(-a\), \(b\), \(-b\) is positive. So we can say that \(J\) contains some positive integers. Let \(S\) denote the set of positive integers in \(J\). That is, \[S=\{na+mb:na+mb>0,\,n,m\in\mathbb{Z}\}.\nonumber\]

By the Well-Ordering Property for \(\mathbb{N}\), \(S\) contains a smallest positive integer, call it \(d\). Let’s show that \(d=\gcd(a,b)\). Note that since \(d\in S\) we have \(d=sa+tb\) for some integers, \(s\) and \(t\). Note also that \(d>0\). Let \(e=\gcd(a,b)\). Then \(e\mid a\) and \(e\mid b\), so by Theorem 3.1 (3) \(e\mid sa+tb\), that is \(e\mid d\). Since \(e\) and \(d\) are positive, by Theorem 3.1 (10) we have \(e\le d\). So if we can show that \(d\) is a common divisor of \(a\) and \(b\) we will know that \(e=d\). To show \(d\mid a\) using the Division Algorithm we write \(a=dq+r\) where \(0\le r<d\). Now \[\begin{split} r &=a-dq \\ &=a-(sa+tb)q \\ &=(1-sq)a+(-tq)b. \end{split}\] Hence \(r\in J\). If \(r>0\) then \(r\in S\). But this cannot be since \(r<d\) and \(d\) is the smallest integer in \(S\). So we must have \(r=0\). That is, \(a=dq\). Hence \(d\mid a\). By a similar argument we can show that \(d\mid b\). Thus, \(d\) is indeed a common divisor of \(a\) and \(b\) since \(d\ge e=\gcd(a,b)\), we must have \(d=\gcd(a,b)\). As noted already \(d=sa+tb\), so the theorem is proved.

Example \(\PageIndex{1}\)

\(1=\gcd(2,3)\) and we have \(1=(-1)2+1\cdot 3\). Also we have \(1=2\cdot 2+(-1)3\). So the numbers \(s\) and \(t\) in Bezout’s Lemma are not uniquely determined. In fact, as we will see later there are infinitely many choices for \(s\) and \(t\) for each pair \(a,b\).

Remark \(\PageIndex{1}\)

The above proof is an existence theorem. It asserts the existence of \(s\) and \(t\), but does not provide a way to actually find \(s\) and \(t\). Also the proof does not give any clue about how to go about calculating \(s\) and \(t\). We will give an algorithm in the next chapter for finding \(s\) and \(t\).