Math 319 Euclidean algorithm
 MATH 319 SPRING 2002

The Euclidean algorithm in Excel

We set up an Excel spreadsheet to duplicate the tables on pages 14 and 15 of NZM.

Column A will be our q column, we'll put r in column B, x in column C, and y in column D.

Assuming the first two values of r (the numbers whose greatest common divisor we want to find) are entered at the top of column B, we want their integer quotient in cell A2, so we enter the formula

=int(B1/B2)

in cell A2.

The third entry in column B should be the remainder from this division. The formula for cell B3 is

=B1-A2*B2

Next, following the explanation in the book (which we are reading closely), we enter 1, 0, 0, and 1 in cells C1, C2, D1, and D2, respectively. According to the algorithm, the entry in cell C3 should be equal to the entry in cell C1 minus q1 times the entry in cell C2. We type

=C1-A2*C2

into cell C3. Similarly, the formula for D3 is

=D1-A2*D2

This completes one iteration of the Euclidean algorithm. Since all cell references are relative, we can effect further iterations simply by copying these formulas down the columns. We do this by highlighting the lowest non-empty cell in each column, dragging the highlight some distance down the column, and entering command-D.

As an example, we now compute (1963,316) by entering these two numbers in the top of column B. The result looks something like this

 A B C D E 1 1963 1 0 2 6 316 0 1 3 4 67 1 -6 4 1 48 -4 25 5 2 19 5 -31 6 1 10 -14 87 7 1 9 19 -118 8 9 1 -33 205 9 #DIV/0! 0 316 -1963 10 #DIV/0! #DIV/0! #DIV/0! #DIV/0!

It appears that

(1963,316)=1
and that
1=-33*1963+205*316.

We can use Excel itself to check our work. If we enter

=C1*\$B\$1+D1*\$B\$2

in cell E1, and then copy this formula down the column, the result should match colum B, the column. We get

 A B C D E 1 1963 1 0 1963 2 6 316 0 1 316 3 4 67 1 -6 67 4 1 48 -4 25 48 5 2 19 5 -31 19 6 1 10 -14 87 10 7 1 9 19 -118 9 8 9 1 -33 205 1 9 #DIV/0! 0 316 -1963 0 10 #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0!

(The dollar signs in this last formula tell Excel to use an absolute reference to cells B1 and B2, so that the formula always computes

1963*(column C entry) + 316*(column D entry).