Exercises 6 through 12 in Chapter 2 deal with the Euclidean algorithm. Work through them using Matlab. Note that you can define the matrices R and L as in Exercise 7 and use them by name in computations. For example, after they have been defined, entering R*L*R^2*L^2*R at the Matlab prompt will immediately verify the answer to Exercise 8(b).
Use `rcop' to see the operation of the Euclidean algorithm in reducing [a b] to [d 0] by successive subtractions. (It is natural to use rcops in which the multiplier b, instead of being -1 is -q, where q is the number of times the smaller of a and b can be subtracted from the larger. This is the way the Euclidean algorithm is described in most modern books.) Subtraction of a from b is multiplication on the right by the inverse of R, and subtraction of b from a is multiplication on the right by the inverse of L. If A is the matrix [a b], and if N is the unimodular matrix given by the algorithm of Section 6 for which AN is diagonal, then the product of Rs and Ls required by Exercise 8 is the inverse of N, which you can find using the command inv(N).
Entering a 1x2 matrix A and applying the algorithm, say by entering the command [D,M,N] = quick(A), is an easy way to generate a 2x2 unimodular matrix. There is a simple formula for the inverse of a 2x2 unimodular matrix. Try several examples and see if you can see the simple relation between the matrix and its inverse.
Pursuant to Exercise 9, try writing 2x2 matrices as products of Rs and Ls. If this can be done, the entries of the matrix can have no negative entries. See if you can find a matrix without negative entries which nonetheless cannot be written as a product of Ls and Rs.
Pick positive integers a and b and try to find by inspection positive integers p and q such that pa = qb + d, as in Exercise 11, where d is the greatest common divisor of a and b. You will find that it is normally hard to do. However, using `quick' you can find p and q immediately. The Euclidean algorithm is an extremely important mathematical idea, and it is worth spending time with.
Return to Chapter 2.