# How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?

-
I'm not sure what you mean. The Extended Euclidean Algorithm is inherently recursive. When you use it by hand, you use it recursively. –  Jim Belk Nov 26 '11 at 18:13
Maybe you can have a look at this question: math.stackexchange.com/questions/20717/… –  Martin Sleziak Nov 26 '11 at 18:14
Have you seen this blurb by KCd? –  Ｊ. Ｍ. Nov 26 '11 at 18:16
If you're looking for help working out examples by hand, you may find this helpful. I certainly find it helpful when writing tests or homework assignments :) –  Bill Cook Nov 26 '11 at 18:41
@Andrew, thanks for taking the time to accept answers in your old questions. –  Jim Belk Nov 26 '11 at 20:06

Perhaps the easiest way to do it by hand is in analogy to Gaussian elimination or triangularization, except that, since the coefficient ring is not a field, one has to use the division / Euclidean algorithm to iteratively descrease the coefficients till zero. In order to compute both $\rm\,gcd(a,b)\,$ and its Bezout linear representation $\rm\,j\,a+k\,b,\,$ we keep track of such linear representations for each remainder in the Euclidean algorithm, starting with the trivial representation of the gcd arguments, e.g. $\rm\: a = 1\cdot a + 0\cdot b.\:$ In matrix terms, this is achieved by augmenting (appending) an identity matrix that accumulates the effect of the elementary row operations. Below is an example from one of my old posts. It computes the Bezout representation for $\rm\:gcd(80,62) = 2\$ viz. $\ 7\cdot 80\: -\: 9\cdot 62\ =\ 2\:.\:$ See this answer for a proof and for conceptual motivation of the ideas behind the algorithm.

For example, to solve  m x + n y = gcd(m,n) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

in equation form   | in row form
---------------------+------------
80 =   1(80) + 0(62) | 80   1   0
62 =   0(80) + 1(62) | 62   0   1
row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
row4 - 4 row5  ->   0 = -31(80) +40(62) |  0 -31  40

The row operations above are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
|    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  when extended to all columns.


In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as 1, and is multiplied by each elementary row operation,
hence it accumulates the product of all the row operations, namely:


$$\left[ \begin{array}{ccc} 7 & -9\\ -31 & 40\end{array}\right ] \left[ \begin{array}{ccc} 80 & 1 & 0\\ 62 & 0 & 1\end{array}\right ] \ =\ \left[ \begin{array}{ccc} 2 & 7 & -9\\ 0 & -31 & 40\end{array}\right ]$$

Notice row 1 is the particular  solution  2 =   7(80) -  9(62)
Notice row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

-
See here for an example in $\rm\color{#940}{TeX}\color{#C00}{ni}\color{#0A0}{color}.\ \$ –  Bill Dubuque Jun 28 '12 at 20:24
Sometimes this is called the Euclid-Wallis algorithm, but I am not sure that is historically correct. –  Bill Dubuque Dec 23 '13 at 22:20

This is more a comment on the method explained by Bill Dubuque then a proper answer in itself, but I think there is an remarque so obvious that I dont understand that it is hardly ever made in texts discussing the extended Euclidean algorithm. This is the observation that you can save youself half of the work by computing only one of the Bezout coefficients. In orther words, instead of recording for every new remainder $r_i$ a pair of coefficients $k_i,l_i$ so that $r_i=k_ia+l_ib$, you need to record only $k_i$ such that $r_i\equiv k_ia\pmod b$. Once you will have found $d=\gcd(a,b)$ and $k$ such that $d\equiv ka\pmod b$, you can then simply put $l=(d-ka)/b$ to get the other Bezout coefficient. This simplification is possible because the relation that gives the next pair of intermediate coefficients is perfectly independent for the two coefficients: say you have \begin{aligned} r_i&=k_ia+l_ib\\ r_{i+1}&=k_{i+1}a+l_{i+1}b\end{aligned} and Euclidean division gives $r_i=qr_{i+1}+r_{i+2}$, then in order to get $$r_{i+2}=k_{i+2}a+l_{i+2}b$$ one can take $k_{i+2}=k_i-qk_{i+1}$ and $l_{i+2}=l_i-ql_{i+1}$, where the equation for $k_{i+2}$ does not need $l_i$ or $l_{i+1}$, so you can just forget about the $l$'s. In matrix form, the passage is from $$\begin{pmatrix} r_i&k_i&l_i\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix} \quad\text{to}\quad \begin{pmatrix} r_{i+2}&k_{i+2}&l_{i+2}\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix}$$ by subtracting the second row $q$ times from the first, and it is clear that the last two columns are independent, and one might as well just keep the $r$'s and the $k$'s, passing from $$\begin{pmatrix} r_i&k_i\\ r_{i+1}&k_{i+1}\end{pmatrix} \quad\text{to}\quad \begin{pmatrix} r_{i+2}&k_{i+2}\\ r_{i+1}&k_{i+1}\end{pmatrix}$$ instead.

A very minor drawback is that the relation $r_i=k_ia+l_ib$ that should hold for every row is maybe a wee bit easier to check by inspection than $r_i\equiv k_ia\pmod b$, so that computational errors could slip in a bit more easily. But really, I think that with some practice this method is just as safe and faster than computing both coefficients. Certainly when programming this on a computer there is no reason at all to keep track of both coefficients.

A final bonus it that in many cases where you apply the extended Euclidean algorithm you are only interested in one of the Bezout coefficients in the first place, which saves you the final step of computing the other one. One example is computing inverse modulo a prime number $p$: if you take $b=p$, and $a$ is not divisible by it, then you know beforehand that you will find $d=1$, and the coefficient $k$ such that $d\equiv ka\pmod p$ is just the inverse of $a$ modulo $p$ that you were after.

-

You may like to check this and this.

Also, there is a well known table method which is very easy and fast for the manual solution.

-

The way to do this is due to Blankinship "A New Version of the Euclidean Algorithm", AMM 70:7 (Sep 1963), 742-745. Say we want $a x + b y = \gcd(a, b)$, for simplicity with positive $a$, $b$ with $a > b$. Set up auxiliary vectors $(x_1, x_2, x_3)$, $(y_1, y_2, y_3)$ and $(t_1, t_2, t_3)$ and keep them such that we always have $x_1 a + x_2 b = x_3$, $y_1 a + y_2 b = y_3$, $t_1 a + t_2 b = t_3$ throughout. The algorithm itself is:

(x1, x2, x3) := (1, 0, a)
(y1, y2, y3) := (0, 1, b)
while y3 <> 0 do
q := floor(x3 / y3)
(t1, t2, t3) := (x1, x2, x3) - q * (y1, y2, y3)
(x1, x2, x3) := (y1, y2, y3)
(y1, y2, y3) := (t1, t2, t3)


At the end, $x_1 a + x_2 b = x3 = \gcd(a, b)$. It is seen that $x_3$, $y_3$ do as the classic Euclidean algorithm, and easily checked that the invariant mentioned is kept all the time.

One can do away with $x_2$, $y_2$, $t_2$ and recover $x_2$ at the end as $(x_3 - x_1 a) / b$.

-
That's the same method as in my answer, and it is much older than Blankinship's 1963 paper. Alas, I don't recall the historical details at the moment. –  Bill Dubuque Mar 24 at 14:54