Associated Topics || Dr. Math Home || Search Dr. Math

```
Date: 07/22/99 at 09:42:27
From: Einar Andresen
Subject: Number Theory / Sum of quadratic residues

Dear Dr. Math,

Maybe this is a bit to advanced - I'll try anyway.

I'm an ex-mathematician trying to refresh my maths on my own. Now I've
read Niven - Zuckerman - Montgomery, _Introduction to the Theory of
Numbers_, 5th edition - and enjoy it.

I solved the problem 3.1.15, essentially showing that if prime
p = 4k+1, then the sum of the quadratic residues in (0,p) equals the
sum of the non-residues.

Question: What happens if p = 4k+3? The difference

d = (sum nonresidues) - (sum residues)

must be divisible by p if p > 3. I used a spreadsheet and found that
d > 0 for n < 1200. The minimum value of d/p, 1, is obtained only for
a few values of p, the largest one being p = 163.

Is it known or easy to prove that d > 0 for all p?
Is it known or easy to prove that d -> infinity when p -> infinity?

Yours sincerely
Einar Andresen, Oslo, Norway
```

```
Date: 07/23/99 at 08:53:11
From: Doctor Rob
Subject: Re: Number Theory / Sum of quadratic residues

Thanks for writing to Ask Dr. Math.

Your question is very interesting. The quantity you have discovered is
quite famous and well known. It is called the class number of the
quadratic number field Q(sqrt[-p]), and is denoted by the letter h.
This is the order of a finite abelian group, called the class group.

Proving this fact is beyond elementary number theory, but can be found
in Borevich and Shafarevich, _Number Theory_, where it is a
consequence of formula (4.3) on p. 344, together with formula (8.5) on
p. 237, by setting d = D = -p = 1 (mod 4), and chi(x) = (x/p), the
Legendre symbol.

Yes, it is known that h > 0, since it is the order of a group, and
must be a positive integer. It is also known that h -> infinity as
p -> infinity. This is a consequence of the fact that for any value
of h, there are only a finite number of p that correspond to it. This
last fact is hard, and only recently proven.

To define the class group of a number field F = Q(alpha), start with
the ring Z[alpha]. Find its integral closure, that is, the set of all
elements of F which are roots of monic polynomials in Z[x]. That is
denoted O_F. That will include Z[alpha], and may be larger or equal to
it. O_F is a commutative ring with 1.

In O_F, look at the set of all ideals. There is a natural way to
define the product of two ideals I and J: I*J is the set of all finite
sums of products formed by an element of I times an element of J.
Under this operation, the ideals form a semigroup.

Define an equivalence relation on the set of ideals in the following
way: if I and J are ideals, then I ~ J iff there exist a and b in O_F
such that (a)*I = (b)*J. This partitions the set of ideals into
equivalence classes. All the principal ideals lie in one of the
classes.

There is a natural multiplicative structure on the classes induced by
multiplication of ideals. If I and J are ideals, and [I] and [J] are
their equivalence classes, then [I]*[J] = [I*J]. You have to check
that this is well-defined (doesn't depend on which I and J in the
class you pick). You can also prove that the set of equivalence
classes with this operation form an abelian group. That's not too
hard.  The hard part is showing that this group is finite. This is the
class group of F mentioned above, and h is its order.

In the case of a quadratic number field F = Q(sqrt[-p]) with p = 3
(mod 4), it turns out that

O_F = Z[sqrt(-p)] = {u+v*sqrt[-p]:u,v in Z}.

Every ideal I can be generated by two elements:

I = (t, u+v*sqrt[-p])

where t, u, and v are in Z, and t | u^2+p*v^2. Now the class number
counts the number of equivalence classes of ideals. All the principal
ideals lie in one class, so h = 1 if and only if every ideal is
principal if and only if there is unique factorization in the ring
O_F = Z[sqrt(-p)]. As you noticed, it turns out that the largest p for
which this ring has unique factorization is p = 163. (This is also
hard to prove, and was done only in the last 20 years, although
something equivalent was conjectured by Gauss [and maybe even Euler].)

Much interesting mathematics springs from the study of class numbers
and class groups. Perhaps you'll see this if you ever study Algebraic
Number Theory.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search