Extra Assignment 2

CS 680-503 Computer Algebra I
Instructor: Jeremy Johnson 

Overview

In Lecture 3, I briefly introduced the domain Z[rho] = {a+b*rho: a,b in Z}. where rho = -1/2 + sqrt(-3)/2. rho is a cube root of unity. I.E. rho^3 = 1. Moreover, rho satisfies the equation x^2+x+1. The other root of x^2+x+1 is rho^2 = -1/2 - sqrt(-3)/2. Let z = a+b*rho, then the norm of z = a+b*rho, N(z) = a^2-a*b+b^2 = (a+b*rho)*a+b*rho^2). The norm is a non-negative integer and N(z*w) = N(z)*N(w). Using the norm, for the map v(), it can be shown that Z[rho] is a Euclidean domain.

To compute the remainder of z = a+b*rho and w = c+d*rho, first compute the quotient in Q[rho]. I.E. z/w = (a+b*rho)*(c+d*rho^2)/(c^2-cd+d^2). Let z/w = R+S*rho, and compute x and y such that x is the nearest integer to R and y is the nearest integer to S. Let q = x+y*rho. Then r = z = q*w, and N(r) < N(w).

Problems to hand in

  1. Show how to multiply two elements in Z[rho].
  2. Show that the norm in Z[rho] is always greater than or equal to 0.
  3. Compute the units in Z[rho], i.e. the elements with multiplicative inverses. HInt, a number in Z[rho] is a unit if and only if its norm is equal to 1.
  4. Let z = a+b*rho and w = c+d*rho be in Z[rho]. Define q = the nearest integer in Z[rho] to z/w = (a+b*rho)*(c+d*rho^2)/(c^2-c*d+d^2) and let r = z - q*w. Show that N(r) < 3/4*N(w).
  5. Implement a maple procedure to compute the gcd of two integers in Z[rho]. You may base your function on the integer version of the Euclidean algorithm presented in class.
    mygcd :=

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