{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 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 12 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 }{CSTYLE "" -1 260 "" 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 4 4 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 4" -1 20 1 {CSTYLE "" -1 -1 "Times " 1 10 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 "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 47 "The Division Algorithm an d Quadratic Extensions" }}{PARA 19 "" 0 "" {TEXT -1 54 "\251Mike May, \+ S.J., maymk@slu.edu, Saint Louis University" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "Mo st of the concepts that we explored with the Gaussian integers can als o be done with the ring Z[" }{XPPEDIT 18 0 "sqrt(d)" "6#-%%sqrtG6#%\"d G" }{TEXT -1 12 "] whenver " }{XPPEDIT 18 0 "0 < d" "6#2\"\"!%\"dG" }{TEXT -1 58 ". As with the Gaussian integers there is an automorphis m " }{XPPEDIT 18 0 "phi" "6#%$phiG" }{TEXT -1 12 " that takes " } {XPPEDIT 18 0 "a + b *sqrt(d)" "6#,&%\"aG\"\"\"*&%\"bGF%-%%sqrtG6#%\"d GF%F%" }{TEXT -1 4 " to " }{XPPEDIT 18 0 "a - b *sqrt(d)" "6#,&%\"aG\" \"\"*&%\"bGF%-%%sqrtG6#%\"dGF%!\"\"" }{TEXT -1 16 ". The norm of " } {XPPEDIT 18 0 "a + b *sqrt(d)" "6#,&%\"aG\"\"\"*&%\"bGF%-%%sqrtG6#%\"d GF%F%" }{TEXT -1 5 " is " }{XPPEDIT 18 0 "abs(a^2 - d*b^2) = abs( (a \+ + b*sqrt(d))*(a-b*sqrt(d)) )" "6#/-%$absG6#,&*$%\"aG\"\"#\"\"\"*&%\"dG F+*$%\"bGF*F+!\"\"-F%6#*&,&F)F+*&F/F+-%%sqrtG6#F-F+F+F+,&F)F+*&F/F+-F7 6#F-F+F0F+" }{TEXT -1 3 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 263 "These extensions of the integers have been stu died a lot. However, most of the results are beyond the scope of this course. For technical reasons, it is easiest to state results if we \+ restrict ourselves to values of D that are not congruent to 1 mod 4. \+ Then Z[" }{XPPEDIT 18 0 "sqrt(d)" "6#-%%sqrtG6#%\"dG" }{TEXT -1 75 "] \+ is a Euclidean Domain with the given norm if and only if d is in the s et " }{XPPEDIT 18 0 "\{2, 3, 6, 7, 11, 19, 55\}" "6#<)\"\"#\"\"$\"\"' \"\"(\"#6\"#>\"#b" }{TEXT -1 61 ". It can be shown that the ring is n ot a UFD if d is one of " }{XPPEDIT 18 0 "\{10, 15, 26, 30\}" "6#<&\"# 5\"#:\"#E\"#I" }{TEXT -1 75 ". These results can be found in standard books on algebraic number theory." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 45 "Generalizing tools from the Gaussian integers" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 163 "We would like to construct the mathematical to ols we used with the Gaussian integers. In particular we would like t o construct the tools for a division algorithm," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "We first need to define " }{XPPEDIT 18 0 "phi" "6#%$ phiG" }{TEXT -1 32 ", the equivalent of conjugation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "phi := x -> subs(sqrt(d)=-sqrt(d),x);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "phi(a + b*sqrt(d));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 30 "Next we want to define a norm:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "normd := x -> abs(expand(x* phi(x)));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "normd(a+b*sqrt (d));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "We would also like func tions for recovering a and b, the rational and irrational parts of a r ing element." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "ratd := x - > (x + phi(x))/2;\nirratd := x -> (x - phi(x))/(2*sqrt(d));\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "ratd(a+b*sqrt(d));\nirratd(a +b*sqrt(d));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 95 "Following the pat tern used with the Gaussian integers, we want to establish a nearest f unction." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "neard := x -> r ound(rationalize(ratd(x))) + round(rationalize(irratd(x)))*sqrt(d);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "neard((a+b*sqrt(d))/(x+y*s qrt(d)));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "This is enough to de fine quotients and remainders over these rings." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 71 "quod := (x,y) -> neard(x/y);\nremd := (x,y) -> expand(x - y*neard(x/y));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 258 24 "The easy cases, d=2 or 3" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "When d is 2 o r 3, the above constructions let us mimic what has we did with the Gau ssian integers. Note that for the Euclidean algorithm to work the rem ainder needs to be smaller than the divisor." }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 105 "Lets see that the definitions work. To do that we nee d a specific value of d. We will start with d = 2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "d := 2;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "We also need to define a u0 and r0 to work with." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "a :=37 + 29 * sqrt(d); b := 3 + 5 \+ * sqrt(d);\n'norm(a)' = normd(a);\n'norm(b)' = normd(b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "Now we find the quatient and the remainde r and check the size of the remainder" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "q0 := quod(a, b); \nr0 := remd(a, b); \n`the norm of r0 ` = normd(r0);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Now we repe at the process until we get a remainder of zero" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 71 "q1 := quod(b, r0); \nr1 := remd(b, r0); \n`th e norm of r1 ` = normd(r1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "q2 := quod(r0, r1); \nr2 := remd(r0, r1); \n`the norm of r2 ` = n ormd(r2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "The last nonzero rem ainder is the GCD." }}}{SECT 0 {PARA 20 "" 0 "" {TEXT -1 0 "" }{TEXT 256 0 "" }{TEXT 257 9 "Exercises" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "1) If d = 2, find the gcd of 85 and " }{XPPEDIT 18 0 "3 + 17*sqrt (d)" "6#,&\"\"$\"\"\"*&\"# " 0 "" {MPLTEXT 1 0 33 "d := 5; normd(1/2 + 1/2*sqrt(d));" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 259 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "3) Verify the the algorithm does not sat isfy the division algorithm when d = 5, " }{XPPEDIT 18 0 "x = 7 + sqrt (d)" "6#/%\"xG,&\"\"(\"\"\"-%%sqrtG6#%\"dGF'" }{TEXT -1 2 ", " } {XPPEDIT 18 0 "y = 6 + 4*sqrt(d)" "6#/%\"yG,&\"\"'\"\"\"*&\"\"%F'-%%sq rtG6#%\"dGF'F'" }{TEXT -1 1 "." }}}{EXCHG }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 57 "A case when the division algorithm requires trickery, d=7 " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "Somewhat contrary to intuitio n, the case of d = 7 is better than when d = 5. We need to recall tha t the size of " }{XPPEDIT 18 0 "a + b* sqrt(d)" "6#,&%\"aG\"\"\"*&%\"b GF%-%%sqrtG6#%\"dGF%F%" }{TEXT -1 8 " is " }{XPPEDIT 18 0 "abs(a^2 - d*b^2))" "6#-%$absG6#,&*$%\"aG\"\"#\"\"\"*&%\"dGF**$%\"bGF)F*!\"\" " }{TEXT -1 57 ". This leads to the interesting observation that when , " }{XPPEDIT 18 0 "0 <= a, b <= 1/2" "6$1\"\"!%\"aG1%\"bG*&\"\"\"F) \"\"#!\"\"" }{TEXT -1 43 " , the origin may not be the closest point. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "The m ethod we have been using to establish the division algorithm is to div ide " }{XPPEDIT 18 0 "x" "6#%\"xG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 " y" "6#%\"yG" }{TEXT -1 11 " producing " }{XPPEDIT 18 0 "alpha = x/y" " 6#/%&alphaG*&%\"xG\"\"\"%\"yG!\"\"" }{TEXT -1 6 " in Q[" }{XPPEDIT 18 0 "sqrt(d)" "6#-%%sqrtG6#%\"dG" }{TEXT -1 14 "], then round " } {XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT -1 4 " to " }{XPPEDIT 18 0 " beta" "6#%%betaG" }{TEXT -1 26 ", the nearest member of Z[" }{XPPEDIT 18 0 "sqrt(d)" "6#-%%sqrtG6#%\"dG" }{TEXT -1 32 "], and show that if t he norm of " }{XPPEDIT 18 0 "alpha - beta" "6#,&%&alphaG\"\"\"%%betaG! \"\"" }{TEXT -1 40 " is less than 1, then the remainder is " } {XPPEDIT 18 0 "y*(alpha - beta)" "6#*&%\"yG\"\"\",&%&alphaGF%%%betaG! \"\"F%" }{TEXT -1 46 ", and this has norm less than the norm of y. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "When d \+ was 2 or 3, we got the ring element closest to " }{XPPEDIT 18 0 "a + b *sqrt(d)" "6#,&%\"aG\"\"\"*&%\"bGF%-%%sqrtG6#%\"dGF%F%" }{TEXT -1 13 " by rounding " }{XPPEDIT 18 0 "a" "6#%\"aG" }{TEXT -1 5 " and " } {XPPEDIT 18 0 "b" "6#%\"bG" }{TEXT -1 111 ". When d = 7, we need to b e more clever. Notice that intuitively bigger ring elements can have \+ smaller norms." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 120 "d := 7; \n`norm (1/2 + 1/2 sqrt(7)) ` = normd (1/2 + 1/2*sqrt(d));\n`norm (3/2 + 1/2 sqrt(7)) ` = normd(3/2 + 1/2*sq rt(d));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "This means that " } {XPPEDIT 18 0 "1/2 + 1/2*sqrt(7)" "6#,&*&\"\"\"F%\"\"#!\"\"F%*(F%F%F&F '-%%sqrtG6#\"\"(F%F%" }{TEXT -1 27 " is closer to -1 than to 0." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "In general, we need to show that g iven any " }{XPPEDIT 18 0 "a + b*sqrt(7)" "6#,&%\"aG\"\"\"*&%\"bGF%-%% sqrtG6#\"\"(F%F%" }{TEXT -1 6 " in Q[" }{XPPEDIT 18 0 "sqrt(7)" "6#-%% sqrtG6#\"\"(" }{TEXT -1 16 "], we can find " }{XPPEDIT 18 0 "m + n * \+ sqrt(7)" "6#,&%\"mG\"\"\"*&%\"nGF%-%%sqrtG6#\"\"(F%F%" }{TEXT -1 6 " i n Z[" }{XPPEDIT 18 0 "sqrt(7)" "6#-%%sqrtG6#\"\"(" }{TEXT -1 24 "] suc h that the norm of " }{XPPEDIT 18 0 "(a-m) + (b-n)*sqrt(7)" "6#,(%\"aG \"\"\"%\"mG!\"\"*&,&%\"bGF%%\"nGF'F%-%%sqrtG6#\"\"(F%F%" }{TEXT -1 22 " has norm less than 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 80 "We first note that it is sufficient by symmetry to c onsider only the cases when " }{XPPEDIT 18 0 "0 <= a, b <= 1/2" "6$1\" \"!%\"aG1%\"bG*&\"\"\"F)\"\"#!\"\"" }{TEXT -1 2 " ." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "We will show that all s uch points are within 1 of either (0,0), or (-1, 0)." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "First consider the points that are within 1 of the \+ origin. Those are the points in the region containing the origin and \+ bounded by the hyperbolas " }{XPPEDIT 18 0 "x^2 - 7*y^2 = 1" "6#/,&*$ %\"xG\"\"#\"\"\"*&\"\"(F(*$%\"yGF'F(!\"\"F(" }{TEXT -1 5 " and " } {XPPEDIT 18 0 "x^2 - 7*y^2 = -1" "6#/,&*$%\"xG\"\"#\"\"\"*&\"\"(F(*$% \"yGF'F(!\"\",$F(F-" }{TEXT -1 82 ". In the region we are concerned w ith, that is the set of points below the curve " }{XPPEDIT 18 0 "y = s qrt((1 + x^2)/7)" "6#/%\"yG-%%sqrtG6#*&,&\"\"\"F**$%\"xG\"\"#F*F*\"\"( !\"\"" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pl ot(\{.5, sqrt((1 + x^2)/7)\}, x = -.1..0.6, y = 0..0.6);\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 241 "As you can see, that gets most of the re gion we are concerned with. We now look at the points within 1 of the point (-1, 0). In terms of our norm, that is the set of points in th e region containing (-1, 0) and bounded by the hyperbolas " } {XPPEDIT 18 0 "(x+1)^2 - 7*y^2 = 1" "6#/,&*$,&%\"xG\"\"\"F(F(\"\"#F(*& \"\"(F(*$%\"yGF)F(!\"\"F(" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "(x+1)^2 - 7*y^2 = -1" "6#/,&*$,&%\"xG\"\"\"F(F(\"\"#F(*&\"\"(F(*$%\"yGF)F(!\" \",$F(F." }{TEXT -1 61 ". Equivalently, it is the set of points betw een the curves " }{XPPEDIT 18 0 "y = sqrt((1 +(x+1)^2)/7)" "6#/%\"yG-% %sqrtG6#*&,&\"\"\"F**$,&%\"xGF*F*F*\"\"#F*F*\"\"(!\"\"" }{TEXT -1 8 " \+ and " }{XPPEDIT 18 0 "y = sqrt((-1 +(x+1)^2)/7" "6#/%\"yG-%%sqrtG6# *&,&\"\"\"!\"\"*$,&%\"xGF*F*F*\"\"#F*F*\"\"(F+" }{TEXT -1 1 "." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "plot(\{sqrt((1 + (x+1)^2)/7) , sqrt((-1 + (x+1)^2)/7)\}, x = -.1..0.6, y = 0..0.6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Putting the curves together, we see that \+ this takes care of all points except for a single point." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "plot(\{sqrt((1 + x^2)/7), sqrt((1 + (x+1)^2)/7), sqrt((-1 + (x+1)^2)/7)\}, x = -.1..0.6, y = 0..0.6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "The only point of concern is t he one on the boundary in both cases. Elementary algebra shows that t his point is " }{XPPEDIT 18 0 "[1/2, sqrt(5)/(2*sqrt(7))]" "6#7$*&\"\" \"F%\"\"#!\"\"*&-%%sqrtG6#\"\"&F%*&F&F%-F*6#\"\"(F%F'" }{TEXT -1 71 ", but that is not a rational point, and does not have to be considered. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 151 "Thus our method of dividing \+ in the associated field and rounding works, we simply have to round t he quotient in the nontrivial fasion described above." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 260 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "4) Use the division algorithm to find the gcd \+ of " }{XPPEDIT 18 0 "98 + 79 * sqrt(7)" "6#,&\"#)*\"\"\"*&\"#zF%-%%sqr tG6#\"\"(F%F%" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "65 + 63*sqrt(7)" "6 #,&\"#l\"\"\"*&\"#jF%-%%sqrtG6#\"\"(F%F%" }{TEXT -1 15 " in the ring Z [" }{XPPEDIT 18 0 "sqrt(7)" "6#-%%sqrtG6#\"\"(" }{TEXT -1 2 "]." }}} {EXCHG }}{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 }