3.3 Bezout’s Identity
If \(a\) and \(b\) are integers (not both \(0\)), then there exist integers \(u\) and \(v\) such that \[\gcd(a,b)=au+bv.\] Moreover \(\gcd(a,b)\) is the least positive integer of the form \(au+bv\;(u, v\in{\mathbb Z })\).
NOTE: The values of \(u\) and \(v\) are not uniquely determined by \(a\) and \(b\).
The proof of Bezout’s Identity will involve sets called ideals.
Note the last requirement says \(I\) is closed under multiplication by all elements of \(R\) not just under multiplication by other elements of \(I\).
We consider the ring \(\mathbb Z\):
- The set \(I=\{0\}\) is an ideal of \(\mathbb Z\).
- The set of even numbers \(I=\{\dots,-2,0,2,4,\dots\}\) is an ideal of \(\mathbb Z\).
- The set of odd numbers is not an ideal (it is not closed under addition, nor is it closed under multiplication by integers).
- The set \(\mathbb N_0\) of non-negative integers is not an ideal (it is closed under addition, but not under multiplication by integers).
Let \(a,b\in\mathbb Z\). Then the set \[I=\{au+bv : u,v\in\mathbb Z\} \] is an ideal in \(\mathbb Z\).
Note: The set \(I\) contains both \(a\) and \(b\): setting \(u=1\) and \(v=0\) we have \(au+bv=a\), while setting \(u=0,v=1\) we get \(au+bv=b\).
Proof. To show \(I\) is an ideal we must prove three things.
\(I\) is non-empty:
Let \(u=v=0\). Then \(au+bv=0\) (by Lemma 2.3) so \(0\in I\).
In particular \(I\) is non-empty.
For \(x,y\) in \(I\), \(x+y\) is also in \(I\):
If \(x\in I\) then there exists \(u,v\) in \(\mathbb Z\) such that \(x=au+bv\).
If \(y\in I\) then there exists \(u',v'\) in \(\mathbb Z\) such that \(y=au'+bv'\).
So \(x+y=au+bv+au'+bv' = (au+au')+(bv+bv')\) by (Comm),(As).
Hence \(x+y=a(u+u')+b(v+v')\) (Dist).
So \(x+y=au''+bv''\) where \(u''=u+u'\) and \(v''=v+v'\) are in \(\mathbb Z\).
Therefore \(x+y\in I\).
For \(x\) in \(I\), \(r\in \mathbb Z\), \(rx\) is also in \(I\):
If \(x\in I\) then there exists \(u,v\) in \(\mathbb Z\) such that \(x=au+bv\).
So \(rx=r(au+bv)=rau+rbv\) by (Dist).
This is \(a(ru)+b(rv)\) by (As),(Comm) so \(rx=au'+bv'\) where \(u'=ru, v'=rv\) are integers.
Hence \(rx\in I\).
Let \(I\) be a non-zero ideal in \(\mathbb Z\). Then there exists \(d\in I\) with \(d\) positive such that \[x\in I \iff d|x\] and \(d\) is the least positive element of \(I\).
Note: this means that \(I\) has the form: \[I=\{nd : n\in\mathbb Z\}\]
Proof. As \(I\) is non-zero it contains some \(x\neq 0\). As \(I\) is an ideal it must also contain \((-1)x=-x\).
Hence \(I\) contains some positive element so the set \(\{x\in I : x>0\}\) has a least element by (WO).
Let \(d\) be the least element of this set, i.e. \(d\) is the least positive element of \(I\).
We will prove: 1. If \(x=nd\) for some \(n\in \mathbb Z\) then \(x\in I\). 2. If \(x\in I\) then f \(x=nd\) for some \(n\in \mathbb Z\).
1. As \(d\in I\), if \(x=nd\) with \(n\in \mathbb Z\) then \(x\in I\) by the definition of ideal.
2. If \(x\in I\) then, by the remainder theorem 3.4 there exists \(q,r\in \mathbb Z\) with \(x=qd+r\) and \(0\leq r<d\).
Since \(d\in I\) and \(-q\in \mathbb Z\) we have \(-(qd)=(-q)d\in I\) by the definition of ideal.
By assumption \(x\in I\) and so as \(qd\in I\) we have \(r=x-qd\) in \(I\).
By definition, \(d\) is the least positive element of \(I\) and \(r<d\) hence \(r\) cannot be positive.
But \(r\geq 0\) so \(r=0\). Thus \(x=qd\) as required.
Proof of Bezout’s Identity
Proof. Let \(I=\{au+bv : u,v\in\mathbb Z\}\). This is an ideal by Lemma 3.18.
So by Lemma 3.19 there is a positive \(d\in I\) such that \(d| x\) for all \(x\in I\).
As \(d\in I\) there exist integers \(u,v\) such that \(d=au+bv\).
As \(a,b\in I\) we have \(d|a\) and \(d|b\), that is \(d\) is a common factor of \(a,b\).
If \(c\) is any other common divisor of \(a,b\) then \(c\) divides \(au+bv=d\) by Corollary 3.11.
Hence \(|c|\leq |d|\) by Lemma 3.9. Since \(|d|=d\) we have \(c\leq |c|\leq d\) for any common divisor \(c\) of \(a,b\).
Thus \(d\) is the greatest common divisor of \(a,b\) so \(\gcd(a,b)=d=au+bv\).
The theorem tells us that \(\gcd(a,b)=au+bv\) has integer solutions, but, like a person in a desert looking for an oasis, knowing that it exists is not as useful as knowing how to find it!
We can use the equations which arise when we apply Euclid’s algorithm to calculate \(d=\gcd(a,b)\):
The penultimate equation, of Euclid’s algorithm has the form \[r_{n-1}-q_{n+1}r_{n} = r_{n+1},\]
Recall that \(d={r_{n+1}}\). So we get \(d={r_{n-1}-q_{n+1}r_{n}}\). Marching back up Euclid’s algorithm we have: \[r_{n}=r_{n-2}-q_{n}r_{n-1},\]
This allows us to eliminate \(r_{n}\)
\[d={r_{n-1}-q_{n+1}(r_{n-2}-q_{n}r_{n-1})}={(1+q_{n-1}q_n)r_{n-1}-q_{n+1}r_{n-2}},\]
- Gradually work backwards through the equations in the algorithm, eliminating \(r_{n-1}, r_{n-2}, \ldots\) in succession.
- eventually we express \(d\) in terms of \(r_1\) and \(r_2\),
- then in terms of \(b\) and \(r_1\),
- and finally in terms of \(a\) and \(b\).
In Example 3.13 we used Euclid’s algorithm to calculate \(d\), where \(a=1815\) and \(b=1415\). Use those equations again to obtain \(u\) and \(v\).
\[ \begin{array}{rcl} 5&=&1\times185-6\times30\\ &=&1\times185-6\times(215-1\times185)\\ &=&7\times185-6\times215\\ &=&7\times(400-1\times215) - 6\times215\\ &=&7\times400-13\times215\\ &=&7\times400-13\times(1414-3\times400)\\ &=&46\times400-13\times1414\\ &=&46\times(1815-1\times1415)-13\times1415\\ &=&46\times1815-59\times1415\\ \end{array} \] and so \(u=46, v=-59\).
Find \(d=\gcd(1068, 4294)\) and express \(d\) in the form \(d=1068u + 4294v\):
First we use Euclid’s algorithm \[ \begin{array}{rcr} 4294&=&4\times1068+22\\ 1068&=&48 \times 22+12\\ 22&=&1 \times 12+10\\ 12&=&1 \times 10+2\\ 10&=&5 \times 2+0\\ \end{array} \]
Next we apply Bezout’s identity \[ \begin{array}{rcl} 2&=&12-10\\ 2&=&12-(22-12)\\ 2&=&2\times12-22\\ 2&=&2\times(1068-48\times22)-22\\ 2&=&2\times1068-97\times22\\ 2&=&2\times1068-97(4294-4\times 1068)\\ 2&=&390\times1068-97\times 4294\\ \end{array} \]
The number of steps in the Euclidean algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.
Proof. Writing \(a=r_0\) and \(b=r_1\) we can apply the Euclidean algorithm to \(a\) and \(b\) to get a sequence of equations. \[ \begin{array}{rclcr} r_0&=&q_1r_1+r_2&&0\le r_2<r_1\\ r_1&=&q_2r_2+r_3&&0\le r_3<r_2\\ r_2&=&q_3r_3+r_4&&0\le r_4<r_3\\ &\ldots&\\ r_{n-3}&=&q_{n-2}r_{n-2}+r_{n-1}&\qquad&0\le r_{n-1}<r_{n-2}\\ r_{n-2}&=&q_{n-1}r_{n-1}+r_{n}&\qquad&0\le r_{n}<r_{n-1}\\ r_{n-1}&=&q_{n}r_{n}\\ \end{array} \]Notice that \(q_1, \ldots,q_{n-1}\ge 1\) and that \(q_n\ge 2\) (as \(r_n<r_{n-1}\)). Consequently we see that \[ \begin{array}{rcl} r_n\ge 1& = &f_2\\ r_{n-1}\ge2r_n\ge 2f_2 & = &f_3\\ r_{n-2}\ge r_{n-1}+r_n\ge f_3+f_2&=&f_4\\ &\ldots&\\ r_2\ge r_3+r_4\ge f_{n-1}+f_{n-2}&=&f_n\\ b = r_1\ge r_2+r_3\ge f_n+f_{n-1}&=&f_{n+1} \end{array} \] But from Example 2.13 we see that \(f_{n+1}\ge \alpha^{n-1}\) for \(n\ge 2\), where \(\alpha = (1+\sqrt{5})/2\). Now since \(\log_{10}\alpha > 1/5\) it follows that \[ \log_{10} b \ge (n-1)\log_{10}\alpha > (n-1)/5. \] If \(b\) has \(k\) decimal digits then \(b< 10^k\) and so \(\log_{10}b< k\). Hence \(n-1< 5k\) and the result follows.
So, for example, if we apply the Euclidean algorithm to integers with 100 digits, then we require no more than 500 steps in the algorithm.
The gcd of a set of integers
Having seen how to calculate the greatest common divisor of two integers, it is a straightforward matter to extend this to any finite set of integers (not all \(0\)). The method, which involves repeated use of Euclid’s algorithm, is based on the following observation.
Prove that for any \(k\ge 2,\) \[\gcd(a_1,\ldots,a_k)=\gcd(\ldots\gcd(\gcd(a_1,a_2), a_3), \ldots, a_k).\]
For example, to calculate \(\gcd(36,24,54,27)\) we calculate \[ \begin{array}{rcrcr} d_2&=&\gcd(36, 24)&=&12\\ d_3&=&\gcd(12, 54)&=&6\\ \text{and finally }d_4&=&\gcd(6, 27)&=&3\\ \end{array} \]
We saw in Example 3.13 that if \(a=1815\) and \(b=1415\) then \(d=5\), so the integers of the form \(c=1815x+1415y\) are the multiples of \(5\). Example 3.20 gives \(5=1815\times46+1415\times(-59)\), so multiplying through by \(e\) we can express any multiple of 5, \(5e\), in the form \(1815x+1415y\): for instance, \(-10=1815\times(-92)+1415\times118\).