Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Quadratic Fields and the Division Algorithm

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--unless I have this wrong--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.

The brute-force way looks too hard to be the right method of proof 

A previous exercise 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 would be the opposite of what you 

  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 

I answered a similar question some time ago, see:

  D is Not Euclidean

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 

  x + yw

with w = (1+sqrt(-7)) / 2.

The argument must be expanded to account for 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, and 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
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994-2015 The Math Forum