Simple Complex Quadratic Fields

For any odd prime p compute the sequence of squares k^2 (mod p) with
k=0,1,2,3,...,p.  For example, with p=19 the squares are

           0,1,4,9,16,6,17,11,7,5,5,7,11,17,6,16,9,4,1,0

Letting C and P denote "composite" and "prime" respectively, this
sequence of squares looks like this:

               0,1,C,C,C,C,P,P,P,P,P,P,P,P,C,C,C,C,1,0

Of course, the sequence of squares is symmetrical because 
k^2 = (p-k)^2 (mod p), so we really only need to consider the 
squares with  k=0,1,2,..,(p-1)/2.  Over this range we notice
that the squares (mod 19) begin with a sequence of composites 
(after 0 and 1) and then the descending sequence of primes
17,11,7,5.  

This pattern of a pure sequence of composites followed by a pure
sequence of primes is really quite unusual.  Normally the prime and
composite residues are scatterred about randomly in the sequence of
squares (mod p).  The only primes (less than 70000) for which the
sequence of square residues has this special structure are listed
below, along with the corresponding central sequences of prime square
residues.  (I'll include the moduli 1 and 2, since their sequences
trivially possess the property of no composites after the first
prime.)

        p                 central sequence
       ---   -----------------------------------------
        1:    -
        2:    1
        3:    1
        7:    2
       11:    5   3
       19:   17  11   7   5
       43:   41  31  23  17  13  11
       67:   59  47  37  29  23  19  17
      163:  151 131 113  97  83  71  61  53  47  43  41

The numbers 1,2,3,7,11,19,43,67,163 are precisely the values d such
that the complex quadratic field K[sqrt(-d)] is 'simple', i.e., the
fields in which the fundamental theorem of arithmetic is true (unique
factorization).

Does anyone know of a proof that the field K[sqrt(-p)] (where p is an
odd prime) is simple if and only if the sequence of square residues
(mod p) has the structure noted above?  Also, is there an analagous
structure that distinguishes the primes p such that the real field
K[sqrt(+p)] has unique factorization?  Can the class number ( > 1) of
any given quadratic field be inferred from the corresponding sequence
of square residues?  What is the significance of the primes in the
central sequence?

[Answers to these questions can be found in some excellent papers 
 by Richard Mollin.  In particular, see "Quadratic Polynomials 
 Producing Consecutive Distinct Primes and Class Groups of Complex 
 Quadratic Fields", which has probably appeared in Acta Arithmetica
 by now.]

Return to MathPages Main Menu