te ri. (c) If ri = 0 then [gcd(m,n) = Ni, STOP]. (d) If ri # 0, set Mi+1 Ni, Ni+1 = Vi. (e) Increase i by one and go to (b). Suppose that we also wish to determine the integer coefficients a and b which are used to combine m and n to give the gcd(m,n). This can be done by keeping track of how mi and Ni can be written in terms of m and n as the algorithm progresses. Let's define (5A.14) (5A.15) As the algorithm is set up, (5A.16) and since Mi+1 = Ni, it follows that A(i+1) = (5A.17) A recursion for B(i+1) can also be determined, using the fact that Ni+1ri=mi-aini (5A.18) Hence, (5A.19) Hence, the modified algorithm for determining gcd(m, n), m > n, is: Revised GCD Algorithm: (a) Let m1 = m, n1 = n, i = Appendix 5A. Finite Field Arithmetic (b) Compute a and ri by Euclid's Division Algorithm. (c) If ri = 0, [gcd(m,n) = Ni = B° m + B2). STOP]. (d) If ri # 0, then compute Mit1,Nith, (i+1) and B(i+1), using the proper recur- sions. (e) Increase i by 1 and go to (b). Further insight into this algorithm can be seen by comparing it to continued fraction computations. Example 5A.5. Find the gcd(46410, 36310300). 36310300 46410 17680 (1,0) (0,1) 46410 17680 11050 (0, 1) (1, - -782) 17680 11050 (1, -782) (-2, 1565) 11050 (-2,1565) (3, -2347) 3,-2347) (-5, 3912) (-5,3912) (8, -6259) Therefore gcd(46410, 36310300) = 2210. Check: 46410 = 21 2210 36310300 = 6430 . 2210 2210 = 8 . 36310300 - 6259 . 46410 5A.3. Polynomials A polynomial P(z) of degree n over a commutative ring R (i.e., with coeffi- cients in R) can be written as (5A.20) The coefficients, ri,i=0,... n, of the polynomial are elements of R. The indeterminate Z obeys all the properties of a commutative ring element with respect to the coefficients; hence Z can be thought of as an element in R or a larger ring containing R. The collection of all polynomials over a ring is itself a ring Rp. Our main interest in polynomial rings is restricted to the case where the coefficients come from a field. A Euclidean division algorithm also exists for polynomials: If P1(z) and P2(z