{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2 " -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 4 4 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 20 "The Gaussian Integer" }} {PARA 19 "" 0 "" {TEXT -1 55 "\251 Mike May, S.J., maymk@slu.edu, Sain t Louis University" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restar t:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 651 "We have been looking at Eu clidean 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 ri ngs, the ring of integers, and the ring of polynomials in one variable over a field, are nice. The problem with keeping things straight ove r 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 a t some other rings where we have to think about the definitions. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "O ne set of examples concerns rings of the form " }{XPPEDIT 18 0 "Z" "6 #%\"ZG" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "sqrt(D)" "6#-%%sqrtG6#%\"DG" } {TEXT -1 204 "] , where D is not a perfect square. These rings are cl ose to the integers and are reasonable to compute with. But just enou gh things change to make life interesting. We will explore those ring s a bit." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 209 "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, wher e a and b are both integers. This ring is called the Gaussian integer s. " }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "Maple has a whole package of routines to look at this rin g." }}{PARA 0 "" 0 "" {TEXT -1 41 "We start by loading the GaussInt pa ckage." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(GaussInt);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 176 "It is worthwhile to check out \+ the help files on GaussInt with the help browser. Keep the help windo w for GaussInt handy. It has links to the specific commands in the pa ckage." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "Recall that Gaussian integers have the form " }{XPPEDIT 18 0 "a + b* I" "6#,&%\"aG\"\"\"*&%\"bGF%%\"IGF%F%" }{TEXT -1 30 " where a and b ar e integers. " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 259 38 "Functions on a single Gaussian integer" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "We start by looking at some of the commands concerned wit h a single Gaussian integer. \n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "Recall that the standard norm function on " }{XPPEDIT 18 0 "Z" " 6#%\"ZG" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "sqrt(D)" "6#-%%sqrtG6#%\"DG" }{TEXT -1 16 "] takes a + b " }{XPPEDIT 18 0 "sqrt(D)" "6#-%%sqrtG6# %\"DG" }{TEXT -1 7 " to " }{XPPEDIT 18 0 "abs(a^2 - Db^2) = abs((a \+ + b sqrt(D))(a - b sqrt(D)))" "6#/-%$absG6#,&*$%\"aG\"\"#\"\"\"*$%#DbG F*!\"\"-F%6#-,&F)F+*&%\"bGF+-%%sqrtG6#%\"DGF+F+6#,&F)F+*&F4F+-F66#F8F+ F." }{TEXT -1 48 ". With the Gaussian integers, we want to take " } {XPPEDIT 18 0 " a + b * I" "6#,&%\"aG\"\"\"*&%\"bGF%%\"IGF%F%" }{TEXT -1 6 " to " }{XPPEDIT 18 0 "a^2 + b^2 = (a+b*I)(a-b*I)" "6#/,&*$%\"a G\"\"#\"\"\"*$%\"bGF'F(-,&F&F(*&F*F(%\"IGF(F(6#,&F&F(*&F*F(F.F(!\"\"" }{TEXT -1 40 ". The Maple command for this is GInorm." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "GInorm(6+12*I);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 223 "Since the Gaussian integers are a Euclidean doma in, and hence a PID and UFD, we can factor any nonzero nonunit elemen t as a product of primes. Recall that primes in the integers need not be prime in the Gaussian integers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "GIfactor(10); GIfactor(17);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 380 "Related to finding the prime factorization of an elem ent, is finding the set of divisors, and the number of divisors of a n umber. Frequently when we list the divisors of an integer, we only gi ve the positive divisors, because the other divisors are associate of \+ elements on the list. In the Gaussian integers, we have 4 units, so M aple only lists divisors in the first quadrant." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 27 "GIdivisor(10); GInodiv(10);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Along the same lines, we can ask whether or no t a Gaussian integer is prime, and how many divisors it has." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "GIprime(5); GInodiv(5); \nGI prime(7); GInodiv(7);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 214 "As we l ook at primes, it is worthwhile to note the Maple has a prime sieve fo r the gaussian integers. It returns the values of all primes with no rm less than or equal to the norm of a specified Gaussian integer. " } }{PARA 0 "" 0 "" {TEXT -1 77 "\n(Actually, you should notice that the \+ list only includes primes of the form " }{XPPEDIT 18 0 "a + b *I" "6#, &%\"aG\"\"\"*&%\"bGF%%\"IGF%F%" }{TEXT -1 48 ", with either b= 0 and a positive, or with 0 < " }{XPPEDIT 18 0 "a <= b" "6#1%\"aG%\"bG" } {TEXT -1 15 ". The prime \000" }{XPPEDIT 18 0 " 1 + I " "6#,&\"\"\"F $%\"IGF$" }{TEXT -1 226 " and the primes that are integers each have \+ 3 associates, the prime times I, -1, and -I. Other primes have 7 rel ated primes, the complex conjugate of the original prime, and I, -1, a nd -I times the prime and its conjugate.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GIsieve(7);" }{TEXT -1 2 " " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 258 10 "Exer cises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "1) Give a criterion fo r primes in Z to remain prime over the Gaussian integers. Make sure y our criterion works on primes up to 30." }}}{EXCHG }{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "2) The primes of Z that are less than 30 \+ and remain prime over the Gaussian integers are ..." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}{EXCHG }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 35 "Divi sion and the Division Algorithm" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "Before we start on division in the Gaussian integers, recall how we d ivide complex numbers. If " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" } {TEXT -1 5 " and " }{XPPEDIT 18 0 "beta" "6#%%betaG" }{TEXT -1 43 " ar e complex numbers, we first note that " }{XPPEDIT 18 0 "beta*conjuga te(beta)" "6#*&%%betaG\"\"\"-%*conjugateG6#F$F%" }{TEXT -1 20 " is r eal, so that " }{XPPEDIT 18 0 "alpha/beta = (alpha*conjugate(beta))/(b eta*conjugate(beta))" "6#/*&%&alphaG\"\"\"%%betaG!\"\"*(F%F&-%*conjuga teG6#F'F&*&F'F&-F+6#F'F&F(" }{TEXT -1 83 ". This reduces complex divi sion to complex multiplication, and division by a real." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 232 "Let's do divison 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 quotie nt." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "x := 3 + 5*I; y := \+ 2 + 1*I;\nyc := conjugate(y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "x*(conjugate(y)); y*(conjugate(y)); x/y; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "nearquo := GInearest(x/y); GIquo(x,y);" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 152 "Having a quotient, we also want \+ to talk about a remainder. We can either do this by multiplying out w hat we rounded off, or by using the GIrem command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "y*nearquo;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "x - y*nearquo; GIrem(x,y);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 149 "Having an algorithm to get a quotient and remainder, w e are set up for the Euclidean algorithm. We we use it to find the gc d of 52 and 19 + 19 I." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "a := 52; b:= 19 + 19*I;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "q[0] := GIquo(a, b); r[0] := GIrem(a, b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "q[1] := GIquo(b, r[0]); r[1] := GIrem(b, r[0]); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "q[2] := GIquo(r[0], r[1 ]); r[2] := GIrem(r[0], r[1]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "q[3] := GIquo(r[1], r[2]); r[3] := GIrem(r[1], r[2]);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "q[4] := GIquo(r[2], r[3]); r [4] := GIrem(r[2], r[3]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Thus the gcd is " }{XPPEDIT 18 0 "r[3] = 1 + I" "6#/&%\"rG6#\"\"$,&\"\"\"F )%\"IGF)" }{TEXT -1 50 ". We get the same result with the Maple comm and." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "GIgcd(a, b);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "As with the integers, we can check this by comparing the prime factorization of a and b." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "GIfactor(a); GIfactor(b);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "Recall that the gcd is also a lin ear combination. Maple lets us recover the coefficients of the linear combination with the GIgcdex command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "GIgcdex(a, b, 'x', 'y');\nprint(x, y);\na*x+b*y;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "We also recall that we can produce a lcm by taking the product and dividing by the gcd." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "GIlcm(a, b);\na*b/GIgcd(a,b);" }}} {SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 257 9 "Exercises" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 193 "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." }}}{EXCHG }{EXCHG }{EXCHG }{EXCHG {PARA 0 "" 0 " " {TEXT -1 69 "4) Use your answer to exercise 2 to find the lcm of th e two numbers." }}}{EXCHG }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 29 "The \+ Chinese Remainder Theorem" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 147 "One \+ of the things we can do in a PID is to use the Chinese Remainder theor em. That theorem says that if we have a finite set of comaximal ideal s (" }{XPPEDIT 18 0 "a[i]" "6#&%\"aG6#%\"iG" }{TEXT -1 27 "), and a se t of remainders " }{XPPEDIT 18 0 "r[i]" "6#&%\"rG6#%\"iG" }{TEXT -1 55 ", we can find an element x such that x is congruent to " } {XPPEDIT 18 0 "r[i]" "6#&%\"rG6#%\"iG" }{TEXT -1 6 " mod (" }{XPPEDIT 18 0 "a[i]" "6#&%\"aG6#%\"iG" }{TEXT -1 98 ") for all i. Consider tha t the case with three comaximal ideals. Then we want to find constant s " }{XPPEDIT 18 0 "m[ij]" "6#&%\"mG6#%#ijG" }{TEXT -1 11 " such that \+ " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "1=m[11]*a[1] + m[12]*a[2]*a[3] " " 6#/\"\"\",&*&&%\"mG6#\"#6F$&%\"aG6#F$F$F$*(&F(6#\"#7F$&F,6#\"\"#F$&F,6 #\"\"$F$F$" }{TEXT -1 4 " , " }{XPPEDIT 18 0 "1=m[21]*a[2] + m[22]*a[ 1]*a[3]" "6#/\"\"\",&*&&%\"mG6#\"#@F$&%\"aG6#\"\"#F$F$*(&F(6#\"#AF$&F, 6#F$F$&F,6#\"\"$F$F$" }{TEXT -1 8 " , and " }{XPPEDIT 18 0 "1 = m[31] *a[3]+m[32]*a[2]*a[1]" "6#/\"\"\",&*&&%\"mG6#\"#JF$&%\"aG6#\"\"$F$F$*( &F(6#\"#KF$&F,6#\"\"#F$&F,6#F$F$F$" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 34 "Then in terms of the congruences, " }}{PARA 0 "" 0 "" {TEXT -1 2 " " }{XPPEDIT 18 0 "m[12]*a[2]*a[3]" "6#*(&%\"mG6#\"#7\"\" \"&%\"aG6#\"\"#F(&F*6#\"\"$F(" }{TEXT -1 17 " = (1, 0 , 0), " } {XPPEDIT 18 0 "m[2,2]*a[1]*a[3]" "6#*(&%\"mG6$\"\"#F'\"\"\"&%\"aG6#F(F (&F*6#\"\"$F(" }{TEXT -1 16 " = (0, 1, 0), " }{XPPEDIT 18 0 "m[3,2]* a[1]*a[2]" "6#*(&%\"mG6$\"\"$\"\"#\"\"\"&%\"aG6#F)F)&F+6#F(F)" }{TEXT -1 13 " = (0, 0, 1)." }}{PARA 0 "" 0 "" {TEXT -1 34 "This means the nu mber we want is " }{XPPEDIT 18 0 "r[1]*m[12]*a[2]*a[3] + r[2]*m[22]*a [1]*a[3] + r[3]*m[32]*a[1]*a[2]" "6#,(**&%\"rG6#\"\"\"F(&%\"mG6#\"#7F( &%\"aG6#\"\"#F(&F.6#\"\"$F(F(**&F&6#F0F(&F*6#\"#AF(&F.6#F(F(&F.6#F3F(F (**&F&6#F3F(&F*6#\"#KF(&F.6#F(F(&F.6#F0F(F(" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 5 "" 0 "" {TEXT -1 7 "Example " }}{PARA 0 "" 0 "" {TEXT -1 96 " Find a Gaussian integer that is con gruent to 1 mod 7, to 2 mod 3 + 4*I, and to 3 mod 1 + 11*I." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "a[1] := 7; a[2] := 3 + 4*I; a[3] := 1 + 11*I; \nr[1] := 1; r[2] := 2; r[3] := 3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 160 "GIgcdex(a[1], a[2]*a[3], 'm[11]', \+ 'm[12]');\nGIgcdex(a[2], a[1]*a[3], 'm[21]', 'm[22]');\nGIgcdex(a[3], \+ a[2]*a[1], 'm[31]', 'm[32]');\nprint(m[12], m[22], m[32]);\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "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];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "This is our answer. We can use GIrem to check our work. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "GIrem(c, a[1]); GIrem( c, a[2]); GIrem(c, a[3]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "We \+ can also do the same thing with the command GIchrem." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "d:=GIchrem( [r[1], r[2], r[3]], [a[1], a[ 2], a[3]]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "This seems to giv e a different answer. We compare c-d with the product a[1]*a[2]*a[3] \+ to see they are equivalent." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "a[1]*a[2]*a[3]; c-d;" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" } {TEXT 256 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 84 "5) With out using GIchrem, find a Gaussian integer that is congruent to 1 mod \+ 1 + I," }}{PARA 0 "" 0 "" {TEXT -1 43 "to 2 mod 3, to 3 mod 2 + I, and to 4 mod 7," }}}{EXCHG }}}{EXCHG }{EXCHG }}{MARK "0 0 0" 0 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }