Assignment 2

CS 680-503 Computer Algebra I
Instructor: Jeremy Johnson 
Due Wed. Jan. 19 in class

 

Overview from Lecture 2

In Lecture 2, we introduced Euclidean domains and talked about the extended Euclidean algorithm. We also discussed unique factorization domains (UFD) and the computation of polynomial gcd's with the Euclidean algorithm and when the Euclidean algorithm is not available with more general polynomial remainder sequences. In the computation of polynomial remainder sequences we observed the concept of intermediate expression swell (i.e. the coefficients of intermediate results contained many digits even though the answer did not).

A Euclidean domain is an integral domain D with a map v from non-zero elements of D into the natural numbers satisfying the following properties:

  1. For all a,b not equal to zero in D, v(ab) >= v(a).
  2. For all a and b in D with b not equal to zero, there exist q and r in D with a = q*b + r and either r = 0 or v(r) < v(b)

Examples of Euclidean domains are:

  1. The integers, Z. v(a) = |a|, the absolute value of a.
  2. The Gaussian integers, Z[i]. Z[i] = {a+bi, a and b in Z, i = sqrt(-1)}. v(a+bi) = a^2 + b^2.
  3. Polynomials with rational number coefficients, Q[x]. A(x) = sum_{i=0}^m a_i * x^i. v(A(x)) = degree(A(x)). More generally, polynomials whose coefficients come from a Field, F, i.e. F[x], are a Euclidean domain using the same function v.

A unique factorization domain (UFD) is an integral domain where every element can be factored uniquely into primes (also called irreducibles). The factorization is unique upto the order of the primes and multiplication by units (elements of the domain with multiplicative inverses). Greatest common divisors always exist in a UFD. We showed this in the first lecture.

We proved that a Euclidean domain is a UFD. Moreover, we can compute gcds using the Euclidean algorithm. This implies that we can compute gcds in Z, Z[i], Q[x] using the Euclidean algorithm as soon as we know how to compute remainders. In class we showed how to compute remainders in all 3 of these domains. The only one that is perhaps unfamiliar is Z[i].

To compute the remainder of z = a+bi and w = c+di, first compute the quotient as a complex number. I.E. z/w = (a+bi)*(c-di)/(c^2+d^2). Then compute the Gaussian integer nearest z/w. Let this number be q, and r = z - q*w. One can show that v(r) < v(w) - see the exercises below.

The Euclidean algorithm can be extended to provide additional information. We showed abstractly that for any a and b in D, a Euclidean domain, there exists x and y in D such that a*x + b*y = gcd(a,b). Moreover, the extended Euclidean algorithm can be used to compute x and y. Let a1 = a, a2 = b, a3,...,a_{n+1} be a remainder sequence for a and b. I.E. a_i = q_i * a_{i+1} + a_{i+2} with v(a_{i+2}) < v(a_{i+2}) and a_{n+2} = 0. Then gcd(a,b) = a_{n+1}. Moreover, if x_1 = 1, x_2 = 0, y_1 = 0, y_2 = 1 and x_{i+2} = x_i - q_i * x_{i+1} y_{i+2} = y_i - q_i * y_{i+1}, then a*x_i + b*y_i = a_i. In particular, x_{n+1} and y_{n+1} provide a solution to a*x+b*y = gcd(a,b).

The maple worksheet accompanying the lecture contained maple implementations of the Euclidean and extended Euclidean algorithm (for the integers and rational polynomials).

As an application of the extended Euclidean algorithm, we provided an algorithm for computing inverses in Z_p. Let a be a nonzero element of Z_p, then gcd(a,p) = 1, and the extended Euclidean algorithm can be used to compute x and y such that a*x + p*y = 1. Reading this equation modulo p, we see that x is the inverse of a. I.E. a*x is equivalent to 1 mod p.

Finally, we remarked that not all UFD's are Euclidean. For example, Z[x], and Q[x,y] are UFD's (gcd's exist) but are not Euclidean. The problem with these domains, is that if you try to compute the remainder using the normal remainder process, you will encounter quotients that are rational numbers or rational functions. Nonetheless, it is possible to compute gcds using the Euclidean algorithm in Q[x] and Q(x)[y] respectively. Q is the field of fractions and Q(x) is the field of rational functions. I will provide additional overview notes on these topics for next lecture - further information is not needed for this exercise.

Problems to hand in

  1. Let z = a+bi and w = c+di be in Z[i]. Define q = the nearest Gaussian integer to z/w = (a+bi)*(c-di)/(c^2+d^2) and let r = z - q*w. Show that v(r) < 1/2*v(w). Note that for any Gaussian integers z and w v(z*w) = v(z)*v(w). Hint show that if q = x + iy and z/w = r + is, that |x-r| <= 1/2 and |y-s| <= 1/2.
  2. Let S = {a + b*sqrt(-5), a, b in Z}. S is an integral domain, but is not a UFD. Show that 21 has two different factorization into primes. Hint for one of the factorizations, let one of the primes be 1 - 2*sqrt(-5). Why is this a prime? You may want to use the norm(a+b*sqrt(-5)) = (a+b*sqrt(-5))*(a-b*sqrt(-5)) = a^2 - 5*b^2. This is exercise 11 from the text.
  3. Let S be defined as in the previous question. Show that the elements 147 and 21-42*sqrt(-5) have no greatest common divisor. Hint: show that 21 is a common divisor and that 7-14*sqrt(-5) is a common divisor. This is exercise 12 from the text.
  4. Use maple's igcdex function to find the inverse of 10 in Z_p, where p = 503. You can use the function ifactor or isprime to verify that 503 is a prime.
  5. Implement a maple procedure to compute the gcd of two Gaussian Integers. The recursive implementation of the Euclidean algorithm from my maple worksheet is:

    mygcd :=

    proc(a,b)
    if b = 0 then RETURN(a) else RETURN(mygcd(b,irem(a,b))) fi
    end;