Skip to main content
Mathematics LibreTexts

1.10: Computing Coefficients for Bezout's Lemma

  • Page ID
    83344
  • \( \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}}\)

    Though the proof of Bezout’s Lemma in the last chapter simply showed that, given integers \(a\) and \(b\), coefficients \(s\) and \(t\) exist such that \(\gcd(a,b)=sa+tb\), suitable modifications of the Euclidean Algorithm give us ways of computing these coefficients. In this chapter we discuss two such ways, known as the Extended Euclidean Algorithm and Blankinship’s Method.

    The Extended Euclidean Algorithm

    With the Extended Euclidean Algorithm, the idea is to rearrange and substitute in the equations arising from the Division Algorithm during the Euclidean Algorithm, so as to arrive at an expression of \(\gcd(a,b)\) as a linear combination of \(a\) and \(b\).

    Suppose that the Euclidean Algorithm produces the following equations: \[\begin{aligned} a &=bq_0+r_0;\\ b &=r_0q_1+r_1;\\ r_0 &=r_1q_2+r_2;\\ &\qquad\vdots\\ r_{k-2} &=r_{k-1}q_k+r_k;\\ r_{k-1} &=r_kq_{k+1}.\end{aligned}\]

    Assuming that \(r_k\) is the last nonzero remainder, we know that \(\gcd(a,b)=r_k\). Suppose that we omit the last equation above and solve the rest of these equations for the remainder term. If we then order them from last to first, we get a new sequence of equations (we show a few more of the last equations in the list):

    \[\begin{aligned} r_k &= r_{k-1}q_k-r_{k-2};\\ r_{k-1} &= r_{k-2}q_{k-1}-r_{k-3};\\ r_{k-2} &= r_{k-3}q_{k-2}-r_{k-4};\\ &\qquad\vdots\\ r_2 &= r_1q_2-r_0;\\ r_1 &= r_0q_1-b;\\ r_0 &= bq_0-a;\\\end{aligned}\]

    Now look at the first of these new equations. Since the Euclidean Algorithm produces \(\gcd(a,b)\), we can actually write \[\label{eqgcd}\gcd(a,b) = r_{k-1}q_k - r_{k-2}.\] Here we see that \(\gcd(a,b)\) is a linear combination of \(r_{k-1}\) and \(r_{k-2}\). Since we’d rather have \(\gcd(a,b)\) as a linear combination of something else (namely, \(a\) and \(b\)), it would be nice to replace \(r_{k-1}\) and \(r_{k-2}\) by expressions involving \(a\) and \(b\). It will take some steps, but this is exactly what we will do.

    Notice that the second equation, \(r_{k-1} = r_{k-2}q_{k-1}-r_{k-3}\), tells us what \(r_{k-1}\) equals. Let’s use this in equation \(\eqref{eqgcd}\), substituting for \(r_{k-1}\); this yields \[\label{eqgcd2} \gcd(a,b) = (r_{k-2}q_{k-1}-r_{k-3})q_k-r_{k-2},\] which we can rearrange as \[\gcd(a,b) = (q_{k-1}q_k - 1)r_{k-2}-q_k r_{k-3}.\nonumber \]

    At this point \(\gcd(a,b)\) is a linear combination of \(r_{k-2}\) and \(r_{k-3}\) (rather than a combination of \(r_{k-1}\) and \(r_{k-2}\), as it was previously). If we make another substitution using the equation \(r_{k-2} = r_{k-3}q_{k-2}-r_{k-4}\), we will get \[\begin{aligned} \gcd(a,b) &= (q_{k-1}q_k - 1)(r_{k-3}q_{k-2}-r_{k-4})-q_k r_{k-3}\\ &= (q_{k-2}q_{k-1}q_k - q_{k-2}-q_k )r_{k-3}-(q_{k-1}q_k - 1)r_{k-4},\end{aligned}\] in which \(\gcd(a,b)\) is now in terms of \(r_{k-3}\) and \(r_{k-4}\).

    At this point the equations are getting messy, so we won’t continue the substitutions (instead, we will work an example below). The idea, however, is simple; by working our way backwards through the equations produced by the Euclidean Algorithm, we can express \(\gcd(a,b)\) as linear combinations that get progressively closer to the linear combination of \(a\) and \(b\) that we need.

    Example \(\PageIndex{1}\)

    For our example, we will continue with the numbers used in Example 1.8.1 from Section 1.8. There we found that \(\gcd(803,154) = 11\). Bezout’s Lemma guarantees that \(11 = 803s+154t\) for some integers \(s,t\). Let us determine a possible choice of \(s\) and \(t\).

    In Example 1.8.1 we found the following: \[\begin{aligned} 803 &=154\cdot5+33 \\ 154 &=33\cdot4+22 \\ 33 &=22\cdot1+11 \\ 22 &=11\cdot2+0.\end{aligned}\]

    Rearranging and reordering all but the last of these equations, we get

    \[\begin{aligned} 11 &=33-22\cdot1\\ 22 &=154-33\cdot4 \\ 33 &= 803-154\cdot5\end{aligned}\]

    We now set about to find an expression of \(11\) as a linear combination of \(803\) and \(154\). Starting with the equation \(11 = 33 - 22\cdot 1\), we substitute \(22=154-33\cdot 4\) (the next equation) to obtain \[\begin{aligned} 11 &= 33 - (154-33\cdot 4)\cdot 1\\ &= 5 \cdot 33 - 1 \cdot 154.\end{aligned}\]

    Now we will substitute for 33, using the equation \(33 = 803-154 \cdot 5\) above: \[1 = 5 \cdot (803-154 \cdot 5) - 1 \cdot 154\nonumber \] and finally obtain \[\boxed{11 = 5 \cdot 803 - 26 \cdot 154.}\nonumber \]

    We have arrived at an expression for \(\gcd(803,154)\) as a linear combination of \(803\) and \(154\), as described by Bezout’s Lemma, with \(s=5\) and \(t=-26\) in the linear combination.

    Blankinship’s Method

    One feature of the Extended Euclidean Algorithm just discussed is that in order to find the coefficients \(s\) and \(t\) in Bezout’s Lemma, we must keep track of quotients and remainders used in carrying out the (original) Euclidean Algorithm, so that we can find \(s\) and \(t\) by “working backwards” through this information once the basic Euclidean Algorithm has ended.

    In this section we see a simple approach to finding \(s\) and \(t\) that appeared in an article by W.A. Blankinship in the August-September 1963 issue of the American Mathematical Monthly.\(^{1}\) As opposed to the Extended Euclidean Algorithm, Blankinship’s method produces the integers \(s\) and \(t\) in Bezout’s Lemma at the same time it produces \(\gcd(a,b)\).

    Given \(a>b>0\) we start with the array \[\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1 \end{bmatrix}\nonumber \] Then we continue to add multiples of one row to another row, alternating choice of rows until we reach an array of the form \[\begin{bmatrix} 0 & x_1 & x_2 \\ d & y_1 & y_2 \end{bmatrix}\nonumber \] or \[\begin{bmatrix} d & y_1 & y_2 \\ 0 & x_1 & x_2 \end{bmatrix}\nonumber \] In other words, the goal is to get a \(0\) in the first column. Once we reach one of these forms, it will be true that \(d=\gcd(a,b)=y_1a+y_2b\).

    Example \(\PageIndex{2}\)

    First take \(a=35\), \(b=15\). \[\begin{bmatrix} 35 & 1 & 0 \\ 15 & 0 & 1 \end{bmatrix}\nonumber \] Note \(35=15\cdot 2+5\), hence \[35+15(-2)=5.\nonumber \] So we multiply row \(2\) by \(-2\) and add it to row \(1\), getting \[\begin{bmatrix} 5 & 1 & -2 \\ 15 & 0 & 1 \end{bmatrix}\nonumber \] Now \(3\cdot 5=15\) or \(15+(-3)5=0\), so we multiply row \(1\) by \(-3\) and add it to row \(2\), getting \[\begin{bmatrix} 5 & 1 & -2 \\ 0 & -3 & 7 \end{bmatrix}.\nonumber \] Now we can say that \[\boxed{\gcd(35,15)=5}\nonumber \] and \[\boxed{5=1\cdot 35+(-2)\cdot 15.}\nonumber \]

    Let’s now consider a more complicated example: Take \(a=1876\), \(b=365\). \[\begin{bmatrix} 1876 & 1 & 0 \\ 365 & 0 & 1 \end{bmatrix}\nonumber \] Now \(1876=365\cdot5+51\) so we add \(-5\) times the second row to the first row, getting: \[\begin{bmatrix} 51 & 1 & -5 \\ 365 & 0 & 1 \end{bmatrix}\nonumber \] Now \(365=51\cdot7+8\), so we add \(-7\) times row \(1\) to row \(2\), getting: \[\begin{bmatrix} 51 & 1 & -5 \\ 8 & -7 & 36 \end{bmatrix}\nonumber \] Now \(51=8\cdot 6+3\), so we add \(-6\) times row \(2\) to row \(1\), getting: \[\begin{bmatrix} 3 & 43 & -221 \\ 8 & -7 & 36 \end{bmatrix}\nonumber \] Now \(8=3\cdot 2+2\), so we add \(-2\) times row \(1\) to row \(2\), getting: \[\begin{bmatrix} 3 & 43 & -221 \\ 2 & -93 & 478 \end{bmatrix}\nonumber \] Then \(3=2\cdot 1+1\), so we add \(-1\) times row \(2\) to row \(1\), getting: \[\begin{bmatrix} 1 & 136 & -699 \\ 2 & -93 & 478 \end{bmatrix}\nonumber \] Finally, \(2=1\cdot 2\) so if we add \(-2\) times row \(1\) to row \(2\) we get: \[\label{eq: Blankenship matrix} \begin{bmatrix} 1 & 136 & -699 \\ 0 & -365 & 1876 \end{bmatrix}.\] This tells us that \[\boxed{\gcd(1876,365)=1}\nonumber \] and \[\label{eq: Blankenship matrix 2} \boxed{1=136\cdot 1876+(-699)365.}\] Note that it was not necessary to compute the last two entries \(-365\) and \(1876\) in equation \(\eqref{eq: Blankenship matrix}\). It is a good idea however to check that equation \(\eqref{eq: Blankenship matrix 2}\) holds. In this case we have: \[\begin{array}{rrr}136\cdot 1876&=&255136 \\ \underline{(-699)\cdot 365}&=&\underline{-255135 } \\ &&1\end{array}\nonumber\] So it is correct.

    Why Blankinship’s Method works: Looking just at what happens in the first column, note that we are carrying out the Euclidean Algorithm, so when one element in column \(1\) is \(0\), the other is, in fact, the \(\gcd\). Note that at the start we have \[\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1 \end{bmatrix}\nonumber \] and \[\begin{aligned} a &=1\cdot a+0\cdot b \\ b &=0\cdot a+1\cdot b.\end{aligned}\] One can show that at every intermediate step \[\begin{bmatrix} a_1 & x_1 & x_2 \\ b_1 & y_1 & y_2 \end{bmatrix}\nonumber \] we always have \[\begin{aligned} a_1 &=x_1a+x_2b \\ b_1 &=y_1a+y_2b,\end{aligned}\] and the result follows. We will omit the details.

    Exercises

    Exercise \(\PageIndex{1}\)

    Use the Extended Euclidean Algorithm to compute the \(s\) and \(t\) in Bezout’s Lemma for each of the following values of \(a\) and \(b\).

    1. \(a=267\), \(b=112\)
    2. \(a=216\), \(b=135\)
    3. \(a=11312\), \(b=11321\)
    Exercise \(\PageIndex{2}\)

    Use Blankinship’s Method to compute the \(s\) and \(t\) in Bezout’s Lemma for each of the pairs \(a,b\) of integers in the previous exercise.

    Exercise \(\PageIndex{3}\)

    Show that if \(1=as+bt\) then \(\gcd(a,b)=1\).

    Exercise \(\PageIndex{4}\)

    Show that whenever \(s,t\) are integers making \(as+bt = \gcd(a,b)\), then \(\gcd(s,t)=1\).

    Exercise \(\PageIndex{5}\)
    1. Find integers \(a\), \(b\), \(d\), \(s\), \(t\) such that all of the following hold
      1. \(a>0\), \(b>0\),
      2. \(d=sa+tb\), and
      3. \(d\ne\gcd(a,b)\).
    2. Explain why the \(d\) you chose in part (a) cannot be \(1\).
    3. What does your example (i.e., the integers \(a,b,d,s,t\)) in part (a) show you about linear combinations of \(a\) and \(b\)?

    Footnotes

    [1] Thanks to Chris Miller for bringing this method to my attention|W.E. Clark.


    This page titled 1.10: Computing Coefficients for Bezout's Lemma is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Barrus & W. Edwin Clark.

    • Was this article helpful?