Date: 08/12/2003 at 23:16:57 From: Mauro Subject: Quadratic Fields and the Division Algorithm How can I prove that there does not exist a division algorithm in any quadratic field K = Q(sqrt(D)), where D <= -15? Basically, I need to prove that, for a and b integers in K such that the norm of a is greater than or equal to the norm of b, there exists an integer c such that the norm of a - bc is less than the norm of b - unless I have this wrong. A previous question asked me to prove that such an algorithm exists for the Gaussian integers, but I did that geometrically, so I have no idea where to go on this one - there are too many cases and variables for me to do it algebraically, I think.
Date: 08/13/2003 at 02:27:36 From: Doctor Jacques Subject: Re: Quadratic Fields and the Division Algorithm Hi Mauro, Actually, what you have to prove is the opposite of what you say: In Q(sqrt(d)), with d <= -15, for some a and b, there is no c such that N(a-bc) < N(b) (otherwise, there would be a division algorithm). An integral domain with a division algorithm is called a Euclidean Domain. I answered a similar question some time ago; see: D is not Euclidean http://mathforum.org/library/drmath/view/62284.html However, a few remarks are in order. In the above article, the question was only about rings of the form Z [sqrt(d)]. As you should know, not all rings of quadratic integers are of that form; for example, for d = -7, the integers are of the form: x + yw with w = (1+sqrt(-7)) / 2 The argument must be expanded to account fot those cases. In particular, it is stated (at the end) that Z[sqrt(-3)] is not Euclidean. This is correct, but that ring is not the largest ring in its field of fractions. The ring of all integers of Q[sqrt(-3)] also includes (1+sqrt(-3))/2, and _that_ ring is Euclidean. If you assume that the Euclidean function is the norm (i.e. the product of the number by its complex conjugate), the reasoning would be based on the same geometric arguments as for the Gaussian integers: you have a division algorithm based on the complex norm if you can cover the plane with open discs of radius 1 centered at the lattice points, as explained in the first part. But there could still be the case that you would have a division algorithm based on another Euclidean function g, defined on the non- zero ring elements, ans satisfying: 1. g(x) is a positive integer 2. If a | b, then g(a) <= g(b) 3. For all a, b, with b <> 0, there exist q and r such that either r = 0 or g(r) < g(b) To show that this is not the case, you have to use the second part of the article. You will also need to fill in what is necessary to cover the cases where d = 1 (mod 4) and the ring contains elements with "half-integer" coordinates. The rings of all integers in Q[sqrt(d)], d < 0, are Euclidean for d = -1, -2, -3, -7, and -11. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum