1.9: Blankinship's Method

In an article in the August-September 1963 issue of the American Mathematical Monthly, W.A. Blankinship\(^{1}\) gave a simple method to produce the integers \(s\) and \(t\) in Bezout’s Lemma and at the same time produce \(\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\] Then \(d=\gcd(a,b)=y_1a+y_2b\). [The goal is to get a \(0\) in the first column.]

Example \(\PageIndex{1}\)

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:1}\begin{bmatrix} 1 & 136 & -699 \\ 0 & -365 & 1876 \end{bmatrix}. \] This tells us that \[\boxed{\gcd(1876,365)=1}\nonumber\] and \[\label{eq:2}\boxed{1=136\cdot 1876+(-699)365.} \] Note that it was not necessary to compute the last two entries \(-365\) and \(1876\) in \(\eqref{eq:1}\). It is a good idea however to check that equation \(\eqref{eq:2}\) holds. In this case we have: \[\begin{aligned} 136\cdot 1876 &= \:255136 \\ \underline{(-699)\cdot 365} &=\underline{-255135} \\ \quad &\quad 1\end{aligned}\] So it is correct.

Why Blankinship’s Method works:

Note that just looking at what happens in the first column you see that we are just doing 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. I will omit the details.

Exercise \(\PageIndex{1}\)

Use Blankinship’s method 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}\)

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

Exercise \(\PageIndex{3}\)

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)\).

Note that \(d\) in Exercise 9.3 cannot be \(1\) by Exercise 9.2.

Footnotes

[1] Thanks to Chris Miller for bringing this method to my attention.