Assignment 1

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

 

Overview from Lecture 1

In the first lecture we introduced the concepts of Ring, Commutative Ring, Integral Domain, Ideal, Quotient Ring, Unique Factorization Domain, Greatest Common Divisors, and Euclidean Domains. The two running examples used were the integers and the integers mod n. We also discussed the Euclidean algorithm for computing greatest common divisors. In this exercise, you will familiarize yourself with some of these concepts. To summarize, a ring R is a set (possibly infinite) with two binary operations (one called plus and the other called multiplication) that satisfies the following properties:
  1. for all a, b in R, a+b is in R.
  2. for all a, b, c in R, (a+b)+c = a+(b+c)
  3. there exists an element 0 in R such that for all a in R a+0 = 0+a = a.
  4. for all a in R there exists an element -a in R such that a + -a = 0 and -a + a = 0.
  5. for all a, b in R, a+b = b+a
  6. for all a, b in R, a*b is in R.
  7. for all a, b, c in R, (a*b)*c = a*(b*c)
  8. there exists an element 1 in R such that for all a in R a*1 = 1*a = a.
  9. for all a, b, c in R, (a+b)*c = a*c + b*c and c*(a+b) = c*a + c*b.
If in addition a*b=b*a for all a and b in R, R is called a commutative ring. If R is a commutative ring with the property that all nonzero elements have multiplicative inverses (i.e. for all a there exists a b in R such that a*b = 1 = b*a) then R is a field. The integers Z are commutative ring but are not a field. The only elements in Z that have multiplicative inverses are 1 and -1. The elements in R that have multiplicative inverses are called units. Even though the integers are not a field, they do have the cancellation property: A commutative ring with this property is called an integral domain. The cancellation property is equivalent to the ring not having any zero divisors. I.E. if a*b = 0 then either a=0 or b=0. In class we showed that a finite integral domain must be a field. We remarked that the integers mod p (Z/p) are a finite integral domain and hence must be a field. After defining a ring, we introduced the notions of an ideal and quotient rings. An ideal I of the ring R is a subset of R with the properties:
  1. for all a,b in I, a+b is in I.
  2. for all a in I and r in R, a*r and r*a are in I.
The definition of quotient ring is reviewed in the exercises. Finally, we introduced the notion of divisors in a commutative ring. a divides b (denoted by a|b) if there exists a c such that b = a*c. A greatest common divisor, c, of a and b, denoted by gcd(a,b) satisfies the properties
  1. c|a and c|b
  2. if d|a and d|b then d|c
A prime is an element p such that the only divisors of p are p itself and units. I.E. if p = a*b, then either a or b must be a unit. A prime is sometimes called an irreducible element. A Unique Factorization Domain (UFD), is an integral domain where each element of the ring can be uniquely factored into primes (uniquenes is upto ordering of the prime factors and multiplication by units). Not all rings have greatest common divisors. We showed that greatest common divisors exist in unique factorization domains. Since the integers are a UFD they have gcd's. We also proved the existence of integer gcds using the Euclidean algorithm. The Euclidean algorithm follows from the key property of the integers:
  1. for all a and b in Z, there exist integers q and r such that a = b*q + r, with 0 <= |r| < |b| [r = rem(a,b)]
Using this property we showed that
  1. gcd(a,b) = gcd(b,r), where r = rem(a,b)
  2. gcd(a,0) = a
These two properties lead to a recursive algorithm for computing gcd(a,b).
IGCD(a,b)
  1. if b = 0 then return a.
  2. return IGCD(b,rem(a,b)).
This algorithm is guaranteed to terminate by the division property which ensures that the remainder gets smaller and hence must eventually equal zero. Tracing through the sequences of this algorithm leads to the following sequence of remainders, called a remainder sequence. Let a = a1 and b = a2. We will assume that a,b >= 0.
  1. a1 = q1*a2 + a3, 0 <= a3 < a2
  2. a2 = q2*a3 + a4, 0 <= a4 < a3
  3. ...
  4. a_{n-1} = q_{n-1}*a_n + a_{n-1}, 0 <= a_{n-1} < a_n
  5. a_n = q_n*a_{n+1}
The gcd(a,b) = a_{n+1}.

Problems to hand in

  1. Let R be a ring and let I be an ideal in R. Define a equivalent to b mod I iff a - b is in I (a equivalent to b mod n in the integers is a special case of this). Show that this defines an equivalence relation. Recall that an equivalence relation must satisfy the following three properties:
    1. a is equivalent to a (reflexivity)
    2. if a is equivalent to b, then b is equivalent to a (symmetry)
    3. if a is equivalent to b and b is equivalent to c then a is equivalent to c (transitivity)
  2. The elements of the quotient ring R/I are the sets I + r, where r is in R (r is called the representative of the set I + r). Note that the set I + r can be represented in many different ways. If r' = r + i for some i in I, then I + r = I + r'. Addition and multiplication in R/I are defined by (I + r1) + (I + r2) = (I + r1 + r2) and (I + r1)*(I + r2) = (I + r1*r2). Show that these operations are well defined. That is that they are independent of the chosen representatives for I + r1 and I + r2. Also show that R/I satisfies the properties of a ring.
  3. Use the Euclidean remainder sequences to prove that if gcd(a,b) = 1 and a|bc then a|c.
  4. Use the result of the previous question to show that Z/p (integers mod p, where p is a prime) is an integral domain. Hint: show that there are no zero divisors.
  5. Show that there are no non-trival ideals in Z/p (i.e. the only ideals are (0) and Z/p itself. Hint, show that for any a, not equal to zero, in Z/p, that (a), the ideal generated by a is equal to Z/p.