The Division Algorithm and Quadratic Extensions\251Mike May, S.J., maymk@slu.edu, Saint Louis Universityrestart;Most of the concepts that we explored with the Gaussian integers can also be done with the ring Z[NiMtJSVzcXJ0RzYjJSJkRw==] whenver NiMyIiIhJSJkRw==. As with the Gaussian integers there is an automorphism NiMlJHBoaUc= that takes NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== to NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiUhIiI=. The norm of NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== is NiMvLSUkYWJzRzYjLCYqJCUiYUciIiMiIiIqJiUiZEdGKyokJSJiR0YqRishIiItRiU2IyomLCZGKUYrKiZGL0YrLSUlc3FydEc2I0YtRitGK0YrLCZGKUYrRjVGMEYr. These extensions of the integers have been studied 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[NiMtJSVzcXJ0RzYjJSJkRw==] is a Euclidean Domain with the given norm if and only if d is in the set NiM8KSIiIyIiJCIiJyIiKCIjNiIjPiIjYg==. It can be shown that the ring is not a UFD if d is one of NiM8JiIjNSIjOiIjRSIjSQ==. These results can be found in standard books on algebraic number theory.

We would like to construct the mathematical tools we used with the Gaussian integers. In particular we would like to construct the tools for a division algorithm,We first need to define NiMlJHBoaUc=, the equivalent of conjugation.phi := x -> subs(sqrt(d)=-sqrt(d),x);phi(a + b*sqrt(d));Next we want to define a norm:normd := x -> abs(expand(x*phi(x)));normd(a+b*sqrt(d));We would also like functions for recovering a and b, the rational and irrational parts of a ring element.ratd := x -> (x + phi(x))/2; irratd := x -> (x - phi(x))/(2*sqrt(d)); ratd(a+b*sqrt(d)); irratd(a+b*sqrt(d));Following the pattern used with the Gaussian integers, we want to establish a nearest function.neard := x -> round(rationalize(ratd(x))) + round(rationalize(irratd(x)))*sqrt(d);neard((a+b*sqrt(d))/(x+y*sqrt(d)));This is enough to define quotients and remainders over these rings.quod := (x,y) -> neard(x/y); remd := (x,y) -> expand(x - y*neard(x/y));

When d is 2 or 3, the above constructions let us mimic what has we did with the Gaussian integers. Note that for the Euclidean algorithm to work the remainder needs to be smaller than the divisor.Lets see that the definitions work. To do that we need a specific value of d. We will start with d = 2.d := 2;We also need to define a u0 and r0 to work with.a :=37 + 29 * sqrt(d); b := 3 + 5 * sqrt(d); 'norm(a)' = normd(a); 'norm(b)' = normd(b);Now we find the quatient and the remainder and check the size of the remainderq0 := quod(a, b); r0 := remd(a, b); `the norm of r0 ` = normd(r0);Now we repeat the process until we get a remainder of zeroq1 := quod(b, r0); r1 := remd(b, r0); `the norm of r1 ` = normd(r1);q2 := quod(r0, r1); r2 := remd(r0, r1); `the norm of r2 ` = normd(r2);The last nonzero remainder is the GCD.

1) If d = 2, find the gcd of 85 and NiMsJiIiJCIiIiomIiM8RiUtJSVzcXJ0RzYjJSJkR0YlRiU=.2) If d = 3, find the gcd of 85 and NiMsJiIiJCIiIiomIiM8RiUtJSVzcXJ0RzYjJSJkR0YlRiU=.

The reason the methods developed for the Gaussian integers work so well in the first two cases is that if d is 2 or 3, then the norm of NiMyLCYlImFHIiIiKiYlImJHRiYtJSVzcXJ0RzYjJSJkR0YmRiZGJg==, whenever the absolute value of both a and b is bounded by NiMqJiIiIkYkIiIjISIi. (Our divisor and remainder method produces a remainder that is NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== times the divisor where NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== is the amount we rounded off to produce our quotient.) This means that the norm of the remainder is less than the norm of the divisor. The method breaks down when d = 5. In that case the norm of NiMvJSZhbHBoYUcsJiomIiIiRiciIiMhIiJGJyooRidGJ0YoRiktJSVzcXJ0RzYjJSJkR0YnRic= is 1. One is tempted to see if NiMlJmFscGhhRw== is closer to other latice points, but if NiMlImFH and NiMlImJH are odd integers, then the norm of NiMqJiwmJSJhRyIiIiomJSJiR0YmLSUlc3FydEc2IyIiJkYmRiZGJiIiIyEiIg== is always at least 1.Part of the problem is that NiMlJmFscGhhRw== is a unit of Q[NiMtJSVzcXJ0RzYjIiIm], so NiMlInlH and NiMqJiUmYWxwaGFHIiIiJSJ5R0Yl try to act like associates with no remainder. It is worthwhile noting that in Z[NiMqJiwmIiIiRiUtJSVzcXJ0RzYjIiImRiVGJSIiIyEiIg==] the given norm is Euclidean.d := 5; normd(1/2 + 1/2*sqrt(d));

3) Verify the the algorithm does not satisfy the division algorithm when d = 5, NiMvJSJ4RywmIiIoIiIiLSUlc3FydEc2IyUiZEdGJw==, NiMvJSJ5RywmIiInIiIiKiYiIiVGJy0lJXNxcnRHNiMlImRHRidGJw==.

Somewhat contrary to intuition, the case of d = 7 is better than when d = 5. We need to recall that the size of NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== is NiMtJSRhYnNHNiMsJiokJSJhRyIiIyIiIiomJSJkR0YqKiQlImJHRilGKiEiIg==. This leads to the interesting observation that when, NiQxIiIhJSJhRzElImJHKiYiIiJGKSIiIyEiIg== , the origin may not be the closest point.The method we have been using to establish the division algorithm is to divide NiMlInhH by NiMlInlH producing NiMvJSZhbHBoYUcqJiUieEciIiIlInlHISIi in Q[NiMtJSVzcXJ0RzYjJSJkRw==], then round NiMlJmFscGhhRw== to NiMlJWJldGFH, the nearest member of Z[NiMtJSVzcXJ0RzYjJSJkRw==], and show that if the norm of NiMsJiUmYWxwaGFHIiIiJSViZXRhRyEiIg== is less than 1, then the remainder is NiMqJiUieUciIiIsJiUmYWxwaGFHRiUlJWJldGFHISIiRiU=, and this has norm less than the norm of y. When d was 2 or 3, we got the ring element closest to NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMlImRHRiVGJQ== by rounding NiMlImFH and NiMlImJH. When d = 7, we need to be more clever. Notice that intuitively bigger ring elements can have smaller norms.d := 7; `norm (1/2 + 1/2 sqrt(7)) ` = normd(1/2 + 1/2*sqrt(d)); `norm (3/2 + 1/2 sqrt(7)) ` = normd(3/2 + 1/2*sqrt(d));This means that NiMsJiomIiIiRiUiIiMhIiJGJSooRiVGJUYmRictJSVzcXJ0RzYjIiIoRiVGJQ== is closer to -1 than to 0.In general, we need to show that given any NiMsJiUiYUciIiIqJiUiYkdGJS0lJXNxcnRHNiMiIihGJUYl in Q[NiMtJSVzcXJ0RzYjIiIo], we can find NiMsJiUibUciIiIqJiUibkdGJS0lJXNxcnRHNiMiIihGJUYl in Z[NiMtJSVzcXJ0RzYjIiIo] such that the norm of NiMsKCUiYUciIiIlIm1HISIiKiYsJiUiYkdGJSUibkdGJ0YlLSUlc3FydEc2IyIiKEYlRiU= has norm less than 1.We first note that it is sufficient by symmetry to consider only the cases when NiQxIiIhJSJhRzElImJHKiYiIiJGKSIiIyEiIg== .We will show that all such points are within 1 of either (0,0), or (-1, 0).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 NiMvLCYqJCUieEciIiMiIiIqJiIiKEYoKiQlInlHRidGKCEiIkYo and NiMvLCYqJCUieEciIiMiIiIqJiIiKEYoKiQlInlHRidGKCEiIiwkRihGLQ==. In the region we are concerned with, that is the set of points below the curve NiMvJSJ5Ry0lJXNxcnRHNiMqJiwmIiIiRioqJCUieEciIiNGKkYqIiIoISIi.plot({.5, sqrt((1 + x^2)/7)}, x = -.1..0.6, y = 0..0.6); As you can see, that gets most of the region 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 the region containing (-1, 0) and bounded by the hyperbolas NiMvLCYqJCwmJSJ4RyIiIkYoRigiIiNGKComIiIoRigqJCUieUdGKUYoISIiRig= and NiMvLCYqJCwmJSJ4RyIiIkYoRigiIiNGKComIiIoRigqJCUieUdGKUYoISIiLCRGKEYu. Equivalently, it is the set of points between the curves NiMvJSJ5Ry0lJXNxcnRHNiMqJiwmIiIiRioqJCwmJSJ4R0YqRipGKiIiI0YqRioiIighIiI= and NiMvJSJ5Ry0lJXNxcnRHNiMqJiwmIiIiISIiKiQsJiUieEdGKkYqRioiIiNGKkYqIiIoRis=.plot({sqrt((1 + (x+1)^2)/7), sqrt((-1 + (x+1)^2)/7)}, x = -.1..0.6, y = 0..0.6);Putting the curves together, we see that this takes care of all points except for a single point.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);The only point of concern is the one on the boundary in both cases. Elementary algebra shows that this point is NiM3JComIiIiRiUiIiMhIiIqJi0lJXNxcnRHNiMiIiZGJSomRiZGJS1GKjYjIiIoRiVGJw==, but that is not a rational point, and does not have to be considered.Thus our method of dividing in the associated field and rounding works, we simply have to round the quotient in the nontrivial fasion described above.

4) Use the division algorithm to find the gcd of NiMsJiIjKSoiIiIqJiIjekYlLSUlc3FydEc2IyIiKEYlRiU= and NiMsJiIjbCIiIiomIiNqRiUtJSVzcXJ0RzYjIiIoRiVGJQ== in the ring Z[NiMtJSVzcXJ0RzYjIiIo].