The Gaussian Integer\251 Mike May, S.J., maymk@slu.edu, Saint Louis Universityrestart:In chapter 8, we have been looking at Euclidean domain, PIDs, and UFDs. The material covers concepts like norm, prime, irreducible, the division algorithm, the Euclidean algorithm, gcd, lcm, and factorization into irreducibles. All of these concepts are attempts to abstract ways in which our favorite two examples of rings, the ring of integers, and the ring of polynomials in one indeterminate over a field, are nice. The problem with keeping things straight over those rings is that we are too familiar with them. We also find that too many terms wind up being equivalent, It is thus useful to look at some other rings where we have to think about the definitions. One set of examples that is developed throughout the exercises in several section of the book concern rings of the form NiMlIlpH[NiMtJSVzcXJ0RzYjJSJERw==] , where D is not a perfect square. These rings are close to the integers and are reasonable to compute with. But just enough things change to make life interesting. We will explore those rings a bit.This worksheet will deal with the first case, when D=-1. Then we are looking at Z[I], the ring of elements of the form a + b I, where a and b are both integers. This ring is called the Gaussian integers. Maple has a whole package of routines to look at this ring.We start by loading the GaussInt package.with(GaussInt);It is worthwhile to check out the help files on GaussInt with the help browser. Keep the help window for GaussInt handy. It has links to the specific commands in the package.Recall that Gaussian integers have the form a + b*I where a and b are integers.

We start by looking at some of the commands concerned with a single Gaussian integer. Recall that the standard norm function on NiMlIlpH[NiMtJSVzcXJ0RzYjJSJERw==] takes a + b NiMtJSVzcXJ0RzYjJSJERw== to NiMvLSUkYWJzRzYjLCYqJCUiYUciIiMiIiIqJCUjRGJHRiohIiItRiU2Iy0sJkYpRisqJiUiYkdGKy0lJXNxcnRHNiMlIkRHRitGKzYjLCZGKUYrRjNGLg==. With the Gaussian integers, we want to take NiMsJiUiYUciIiIqJiUiYkdGJSUiSUdGJUYl to NiMvLCYqJCUiYUciIiMiIiIqJCUiYkdGJ0YoLSwmRiZGKComRipGKCUiSUdGKEYoNiMsJkYmRihGLSEiIg==. The Maple command for this is GInorm.GInorm(6+12*I);Since the Gaussian integers are a Euclidean domain, and hence a PID and UFD, we can factor any nonzero nonunit element as a product of primes. Recall that primes in the integers need not be prime in the Gaussian integers.GIfactor(10); GIfactor(17);Related to finding the prime factorization of an element, is finding the set of divisors, and the number of divisors of a number. Frequently when we list the divisors of an integer, we only give the positive divisors, because the other divisors are associate of elements on the list. In the Gaussian integers, we have 4 units, so Maple only lists divisors in the first quadrant.GIdivisor(10); GInodiv(10);Along the same lines, we can ask whether or not a Gaussian integer is prime, and how many divisors it has.GIprime(5); GInodiv(5); GIprime(7); GInodiv(7);As we look at primes, it is worthwhile to note the Maple has a prime sieve for the Gaussian integers. It returns the values of all primes with norm less than or equal to the norm of a specified Gaussian integer. (Actually, you should notice that the list only includes primes of the form NiMsJiUiYUciIiIqJiUiYkdGJSUiSUdGJUYl, with either b= 0 and a positive, or with 0 < NiMxJSJhRyUiYkc=. The prime NiMsJiIiIkYkJSJJR0Yk and the primes that are integers each have 3 associates, the prime times I, -1, and -I. Other primes have 7 related primes, the complex conjugate of the original prime, and I, -1, and -I times the prime and its conjugate.)GIsieve(7);

1) Give a criterion for primes in Z to remain prime over the Gaussian integers. Make sure your criterion works on primes up to 30.Th criterion is ...2) The primes of Z that are less than 30 and remain prime over the Gaussian integers are ...

Before we start on division in the Gaussian integers, recall how we divide complex numbers. If NiMlJmFscGhhRw== and NiMlJWJldGFH are complex numbers, we first note that NiMqJiUlYmV0YUciIiItJSpjb25qdWdhdGVHNiNGJEYl is real, so that NiMvKiYlJmFscGhhRyIiIiUlYmV0YUchIiIqKEYlRiYtJSpjb25qdWdhdGVHNiNGJ0YmKiZGJ0YmRipGJkYo. This reduces complex division to complex multiplication, and division by a real.The exercises in the book suggest that we do division of Gaussian integers by dividing them as complex numbers and taking the nearest Gaussian integer as the quotient. We can do this either with the GIquo command, or with the GInearest command on the complex quotient.x := 3 + 5*I; y := 2 + 1*I; yc := conjugate(y);x*(conjugate(y)); y*(conjugate(y)); x/y; nearquo := GInearest(x/y); GIquo(x,y);Having a quotient, we also want to talk about a remainder. We can either do this by multiplying out what we rounded off, or by using the GIrem command.y*nearquo;x - y*nearquo; GIrem(x,y);Having an algorithm to get a quotient and remainder, we are set up for the Euclidean algorithm. We we use it to find the gcd of 52 and 19 + 19 I.a := 52; b:= 19 + 19*I;q[0] := GIquo(a, b); r[0] := GIrem(a, b);q[1] := GIquo(b, r[0]); r[1] := GIrem(b, r[0]);q[2] := GIquo(r[0], r[1]); r[2] := GIrem(r[0], r[1]);q[3] := GIquo(r[1], r[2]); r[3] := GIrem(r[1], r[2]);q[4] := GIquo(r[2], r[3]); r[4] := GIrem(r[2], r[3]);Thus the gcd is NiMvJiUickc2IyIiJCwmIiIiRiklIklHRik=. We get the same result with the Maple command.GIgcd(a, b);As with the integers, we can check this by comparing the prime factorization of a and b.GIfactor(a); GIfactor(b);Recall that the gcd is also a linear combination. Maple lets us recover the coefficients of the linear combination with the GIgcdex command.GIgcdex(a, b, 'x', 'y'); print(x, y); a*x+b*y;We also recall that we can produce a lcm by taking the product and dividing by the gcd.GIlcm(a, b); a*b/GIgcd(a,b);

3) Find the GCD of 1257 + 2923*I and 296 + 185*I by the Euclidean algorithm. (Don't use the GIgcd or GIgcdex commands.) Check your answer by doing prime factorizations of the two numbers.The gcd is....4) Use your answer to exercise 2 to find the lcm of the two numbers.

One of the things we can do in a PID is to use the Chinese Remainder theorem. That theorem says that if we have a finite set of comaximal ideals (NiMmJSJhRzYjJSJpRw==), and a set of remainders NiMmJSJyRzYjJSJpRw==, we can find an element x such that x is congruent to NiMmJSJyRzYjJSJpRw== mod (NiMmJSJhRzYjJSJpRw==) for all i. Consider that the case with three comaximal ideals. Then we want to find constants NiMmJSJtRzYjJSNpakc= such that NiMvIiIiLCYqJiYlIm1HNiMiIzZGJCYlImFHNiNGJEYkRiQqKCZGKDYjIiM3RiQmRiw2IyIiI0YkJkYsNiMiIiRGJEYk , NiMvIiIiLCYqJiYlIm1HNiMiI0BGJCYlImFHNiMiIiNGJEYkKigmRig2IyIjQUYkJkYsNiNGJEYkJkYsNiMiIiRGJEYk , and NiMvIiIiLCYqJiYlIm1HNiMiI0pGJCYlImFHNiMiIiRGJEYkKigmRig2IyIjS0YkJkYsNiMiIiNGJCZGLDYjRiRGJEYk.Then in terms of the congruences, NiMqKCYlIm1HNiMiIzciIiImJSJhRzYjIiIjRigmRio2IyIiJEYo = (1, 0 , 0), NiMqKCYlIm1HNiQiIiNGJyIiIiYlImFHNiNGKEYoJkYqNiMiIiRGKA== = (0, 1, 0), NiMqKCYlIm1HNiQiIiQiIiMiIiImJSJhRzYjRilGKSZGKzYjRihGKQ== = (0, 0, 1).This means the number we want is NiMsKCoqJiUickc2IyIiIkYoJiUibUc2IyIjN0YoJiUiYUc2IyIiI0YoJkYuNiMiIiRGKEYoKiomRiZGL0YoJkYqNiMiI0FGKCZGLkYnRihGMUYoRigqKiZGJkYyRigmRio2IyIjS0YoRjlGKEYtRihGKA==.Example Find a Gaussian integer that is congruent to 1 mod 7, to 2 mod 3 + 4*I, and to 3 mod 1 + 11*I.a[1] := 7; a[2] := 3 + 4*I; a[3] := 1 + 11*I; r[1] := 1; r[2] := 2; r[3] := 3;GIgcdex(a[1], a[2]*a[3], 'm[11]', 'm[12]'); GIgcdex(a[2], a[1]*a[3], 'm[21]', 'm[22]'); GIgcdex(a[3], a[2]*a[1], 'm[31]', 'm[32]'); print(m[12], m[22], m[32]); c:= r[1]*m[12]*a[2]*a[3]+r[2]*m[22]*a[1]*a[3]+r[3]*m[32]*a[1]*a[2];This is our answer. We can use GIrem to check our work.GIrem(c, a[1]); GIrem(c, a[2]); GIrem(c, a[3]);We can also do the same thing with the command GIchrem.d:=GIchrem( [r[1], r[2], r[3]], [a[1], a[2], a[3]]);This seems to give a different answer. We compare c-d with the product a[1]*a[2]*a[3] to see they are equivalent.a[1]*a[2]*a[3]; c-d;

5) Without using GIchrem, find a Gaussian integer that is congruent to 1 mod 1 + I,to 2 mod 3, to 3 mod 2 + I, and to 4 mod 7,