Sum of Quadratic ResiduesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/