MATH 319 |
SPRING 2002 |

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

Column A will be our

qcolumn, we'll putrin column B,xin column C, andyin 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

qtimes the entry in cell C2. We type_{1}=C1-A2*C2into 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

ABCDE11963 1 0 26 316 0 1 34 67 1 -6 41 48 -4 25 52 19 5 -31 61 10 -14 87 71 9 19 -118 89 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 that1=-33*1963+205*316. We can use Excel itself to check our work. If we enter

=C1*$B$1+D1*$B$2in cell E1, and then copy this formula down the column, the result should match colum B, the

column. We get

ABCDE11963 1 0 1963 26 316 0 1 316 34 67 1 -6 67 41 48 -4 25 48 52 19 5 -31 19 61 10 -14 87 10 71 9 19 -118 9 89 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).