# 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

- Show how to multiply two elements in Z[rho].
- Show that the norm in Z[rho] is always greater than or equal to 0.
- 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.
- 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).
- 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;