Primitive Roots of Primes

Date: 06/05/2005 at 01:10:47
From: Sadanand
Subject: Primitive roots of primes

I define the Primitive Roots Index (PRI) of a prime p as the [sum of 
all its p.r.’s] mod p.  A surprising property of PRI which I stumbled 
upon is its value is always 0, + 1, - 1 for all primes.  In 
particular, for primes of the form (4m + 1), it is always 0 (a fact
which I found easy to prove).  For primes of the form (4m – 1), it can
assume any of the possible values.  My questions are:
 
1) Is it possible to prove this property for all primes?

2) Is it possible to derive the PRI as a function of the value of p?

I shall be grateful for any specific web site references on these 
questions, along with your response.

Here are the first 50 primes with their corresponding PRI's:

  p   =  2    3    5    7    11   13   17   19    23    29
  PRI = -1   -1    0   +1   +1    0    0    0    +1     0

  p   =  31   37   41   43   47   53   59   61    67    71
  PRI = -1    0    0   -1   +1    0   +1    0    -1    -1

  p   =  73   79   83   89   97   101  103  107   109   113
  PRI =  0   +1   +1    0    0    0   -1   +1     0     0

  p   =  127  131  137  139  149  151  157  163   167   173
  PRI =  0   -1    0   -1    0    0    0    0    +1     0

  p   =  179  181  191  193  197  199  211  223   227   229
  PRI = +1    0   -1    0    0    0   +1   -1    +1     0

Date: 06/12/2005 at 05:40:31
From: Doctor Jacques
Subject: Re: Primitive Roots of Primes

Hi Sadanand,

Your guess is correct; however, the proof involves some non-elementary 
concepts you may be unfamiliar with.  If this is the case, you may 
have to do some additional research by yourself; although I can give 
you some assistance, I can hardly give you here a complete course on 
the subject.

In any field, an element x is called an n-th root of unity if it 
satisfies the equation x^n - 1 = 0.  It is called a primitive n-th 
root of unity if it satisfies the above equation, but no other 
similar equation of lower degree.

To put it otherwise, we can define the order o(x) of an element x as 
the smallest positive integer n such that x^n = 1; a primitive n-th 
root of unity is an element of order n.

The product of all factors (x - r_i), where r_i ranges over all 
elements of order n is called the cyclotomic polynomial of order n, 
and written F_n(x).  You can read more about this on:

  Cyclotomic Polynomial
    http://mathworld.wolfram.com/CyclotomicPolynomial.html 

If p is a prime, all elements of the field Zp satisfy the equation
x^(p-1) = 1, by Fermat's theorem.  The primitive roots modulo p are 
those elements x for which (p-1) is the smallest exponent such that 
the above equation is satisfied--they are precisely the primitive
(p-1)-th roots of unity.

If the primitive roots are r_1, ..., r_k, they are therefore the roots 
(over Zp) of the cyclotomic polynomial F_(p-1)(x).  As you should 
know, the sum of the roots of a monic polynomial is the negative of 
the coefficient of the second term; in this case, this sum is what you 
called PRI.

Note that, if r is a primitive n-th root of unity, then r^k is also a 
primitive root if and only if gcd(k,n) = 1.

By grouping n-th roots of unity according to their order, it is easy 
to see that we have a factorization:

  x^n - 1 = PRODUCT (F_d(x))      [1]

where the product ranges over all divisors d of n.  By using the 
inclusion-exclusion principle (or a more sophisticated version of it, 
called the Möbius inversion formula), it is possible to compute the 
F_d(x) recursively, using only rational operations.  This shows that 
the coefficients of those polynomials are integers, and do not depend 
on the particular field under consideration (in many cases, those 
integers are 0, 1, and -1, but this is not always true--the smallest 
counter-example occurs with F_105(x)).

The cyclotomic polynomials verify many interesting identities; in 
this case, we are mainly concerned with the formulas (29) and (30) in 
the above article.

Formula (29) says:

  F_np(x) = F_n(x^p)

if p divides n.  This means that, if k is divisible by the square of a 
prime p, F_k is a polynomial in x^p, and the second coefficient will 
be 0.  In particular, if q = 4m + 1 is prime, then q-1 is divisible by 
2^2, and F_(q-1)(x) is a polynomial in x^2, which implies that the PRI 
(equal to minus the coefficient of the second term) is 0, as you 
already showed (in this particular case, there is an easier way to 
show this).  More generally, if q-1 is divisible by a square, (i.e. 
has a repeated prime factor), then PRI(q) = 0.

Let us now forget about primitive roots of primes, and concentrate on 
cyclotomic polynomials.

We will write s(n) = the coefficient of the second term of F_n(x).  If 
n+1 is prime, s(n) = -PRI(n+1).

Formula (30) says:

  F_np(x) = F_n(x^p)/F_n(x)

if p does not divide n.  If you look at what this means in terms of 
polynomial long division, you will see that this implies that:

  s(np) = -s(n)       [2]

On the other hand, if n is prime, formula [1] reduces to:

  x^n - 1 = F_1(x)*F_n(x)
          = (x - 1) * F_n(x)

which shows that:

  F_n(x) = (x^n - 1)/(x - 1)
         = x^(n-1) + x^(n-2) + ... + 1

and s(n) = 1 (the coefficient of x^(n-2)).

By using formula [2] recursively, we conclude that, if n is not 
divisible by a square, we have:

  s(n) = (-1)^(k+1)

where k is the number of (distinct by hypothesis) prime factors of n.

As PRI(q) = -s(q-1), we can summarize the results as:

* If (q-1) has a repeated prime factor, PRI(q) = 0

* Otherwise, PRI(q) = (-1)^k, where k is the number of prime factors
  of q-1.

By the way, the negative of the function s(n) above is called the 
Möbius function, and has many applications in number theory.  See, for 
example:

  Möbius Function 
    http://mathworld.wolfram.com/MoebiusFunction.html  

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/ 

Date: 06/18/2005 at 07:24:52
From: Sadanand
Subject: Primitive roots of primes

Hi Doc,

I have generally followed the drift of your arguments in the reply to 
my question.  However, I have some doubts which I would like to get 
resolved.

1) The cyclotomic polynomials are defined in the field of complex 
numbers.  For arguments based on these to be used in the field of mod 
p integers, which has been designated as Zp, there has to be some
correspondence between the elements of the complex number field and
Zp, with respect to the operations of multiplication as well as 
addition.  I am able to see only a partial correspondence w.r.t 
multiplication, but not w.r.t. addition. 

2) The truth of Formula [1] used by you, namely, (x^n) – 1 = Product 
[Fd(x)] where the product is taken over all divisors of n (including 
1 and itself), is almost self-evident.  But not so are the formulas 
(29) and (30) of the reference cited by you.  As the proof of 
expression for PRI seems to vitally depend on these 2 formulas, I 
would like to know whether there is some simple explanation as to how 
they arise.

Sadanand

Date: 06/19/2005 at 05:34:10
From: Doctor Jacques
Subject: Re: Primitive roots of primes

Hi again Sadanand,

The definition of cyclotomic polynomials used in MathWorld's reference 
is based on complex numbers, because it makes things more intuitive
("a little inaccuracy can save tons of explanations"), but it is
possible to define them more generally, and the resulting polynomials
do not depend on the particular field you use.  In fact, everything
relies on the analysis of the equation x^n = 1.

I'll try to give you a feeling of the ideas that are involved, 
although, as I said before, a complete treatment would fill a whole 
textbook; in fact, this even leads to Galois Theory.

There are some facts that are valid over any field:

* A polynomial of degree n cannot have more than n roots in the field.

* x^k - 1 divides x^n - 1 if and only if k divides n.

* Any finite subgroup of the multiplicative group of a field is
  cyclic.  This means that, if S is a finite subset of a field K,
  closed under multiplication and inverses, then S consists of all
  the powers of a single element, called a primitive element (for Zp,
  such an element is a primitive root modulo p).

Another important fact is that, given a field K (like Q, R, Zp, ...) 
and an irreducible polynomial f(x) over K, it is always possible to 
construct an extension of K (a field L containing K) such that f(x) 
has a root in L.  (I believe this construction is attributed to 
Kronecker).

This is how the complex numbers can be constructed.  You start with 
the field R of real numbers, and the irreducible polynomial x^2 + 1. 
You can then create the field C by including a root of f(x), which you 
call i.

This process is quite general.  Given K and f(x) as before, the field 
L is the set of equivalence classes of polynomials over K, modulo 
f(x).  The fact that each element (polynomial) has an inverse comes 
from the fact that we assumed f(x) irreducible.  This means that, for 
any element g(x) of L, not congruent to 0 mod f(x), we have
gcd(f(x),g(x)) = 1, and we can use the Extended Euclidean Algorithm 
to find polynomials u(x) and v(x) (over K) such that:

  g(x)u(x) + f(x)v(x) = 1

which means that g(x)u(x) = 1 (mod f(x)), so that u(x) is the inverse 
of g(x) in L.

In the case of C, we can define complex numbers as real polynomials 
modulo x^2 + 1.  The complex number a + bi corresponds to the 
equivalence class of the polynomial [bx + a] (mod (x^2 + 1)).  You can 
check that all the usual operations on complex numbers check out
nicely.  Once we know that the construction is possible, it is more 
practical to define a symbol (i in this case) to represent the 
equivalence class of the polynomial [x], and to say that C is 
constructed by adjoining i to the base field (R).  We write C = R(i) 
to express this.

You can use this construction over any field.  For example, the 
polynomial f(x) = x^2 - 2 is irreducible over Q (the rationals).  You 
can create an extension L in which f(x) has a root, by defining it as 
the equivalence classes of rational polynomials modulo f(x); in this 
case, the polynomial [x] corresponds to sqrt(2), since we have:

  [x]^2 - 2 = [x^2 - 2] = 0 (mod f(x))

which shows that [x] is indeed a root of f(x).  We have extended Q by 
adjoining the element sqrt(2), giving Q(sqrt(2)).

There are some subtleties in this (although they do not arise in 
finite fields).  The point is that the field L constructed as above 
contains at least one root of f(x), but not necessarily all of them. 
For example, if you start with the field Q and the irreducible 
polynomial f(x) = x^3 - 2, the polynomial has three complex roots, 
one of which is real.  If you take a to be the real root, Q(a) does 
not contains the other two roots, since Q(a) only contains real 
numbers.  In fact, over Q(a), you have the factorization;

  x^3 - 2 = (x - a)(x^2 * ax + a^2)

where the second factor is still irreducible.  To get a complete 
factorization, you have to repeat the process by extending Q(a) with a 
root of the second factor--this gives you a larger field (still 
containing Q) that contains all the roots of f(x).

If the polynomial f(x) is not irreducible, you can also construct a 
chain ("tower") of extensions, by adjoining one root at a time.

The important conclusion of all this is:

For any field K, and any polynomial f(x) over K, there exists a field 
L containing K and containing all the roots of f(x) (the smallest such 
field is called a splitting field of f(x) over K).  We can therefore 
assume that any polynomial over K is the product of linear factors in 
some suitable extension field, and this justifies some of the 
arguments we use.

For an example more related to the case at hand, consider the field 
Z5.  Over Z5, the polynomial x^3 - 1 factorizes as:

  x^3 - 1 = (x - 1)(x^2 + x + 1)   [1]

We see that there is one root in the field (x = 1), but the second 
factor is irreducible over Z5.  We create an extension L of Z5 as the 
class of polynomials over Z5 modulo f(x) = x^2 + x + 1.

Each element of L is an equivalence class of polynomials modulo f(x). 
By dividing by f(x) (of degree 2), we see that such an equivalence 
class contains a uniquely determined representative of the form
ax + b.  Because a and b are elements of Z5, there are 5 possibilities 
for each, and L contains 5^2 = 25 elements; this field is usually 
denoted by GF(25), where GF stands for "Galois Field".  (This is NOT 
Z_25, the integers modulo 25, which is merely a ring, but not a field, 
since 5 has no inverse in Z_25.)  If we denote by u the equivalence 
class of the polynomial [x], we have, by construction,

  f(u) = u^2 + u + 1 = 0

and the three roots of x^3 - 1 are 1, u, and u^2 = - u - 1.

All this shows (at the expense of a lot of missing steps in the 
argument) that the definition of cyclotomic polynomials is legitimate 
over any field--there is always a suitable extension field that 
contains the appropriate roots of unity.  (Note that we did not yet 
prove that the polynomials themselves do not depend on the chosen 
field, which is only partially true, and will be shown later.)

Note that the factorization [1] is valid over any field, and this
shows that F_3(x) = x^2 + x + 1, independently of the selected field 
(more on this later).  However, if we work in Z7 instead of Z5, the 
second factor is no longer irreducible, and we have:

  x^3 - 1 = (x - 1)(x - 2)(x - 4)

and, over Z7, we have:

  F_3(x) = x^2 + x + 1 = (x - 2)(x - 4)

This shows that, although we always have F_3(x) = x^2 + x + 1, the 
factorization of that polynomial depends on the selected field.  In 
particular, it can be shown (this is hard...) that the cyclotomic 
polynomials are always irreducible over Q.

Let us now look at how we can compute the cyclotomic polynomials in 
practice, and assume we want to compute F_6(x). (We left the field 
unspecified for the moment, and we will show that it does not matter.)

If x^6 = 1, the order of x must be 1, 2, 3, or 6.  This means that x 
is a root of F_1(x), F_2(x), F_3(x), or F_6(x).  We have:

  x^6 - 1 = F_1(x)*F_2(x)*F_3(x)*F_6(x)   [3]

and we try to find the last factor.  Obviously, we have:

  F_1(x) = x - 1                [4]

by definition.  As we have, using a similar argument;

  x^2 - 1 = F_1(x)*F_2(x)

this gives:

  F_2(x) = (x^2 - 1)/F_1(x)
         = x + 1                [5]

In the same way, we find:

  x^3 - 1 = F_1(x)*F_3(x)
  F_3(x)  = (x^3 - 1)/F_1(x)
          = x^2 + x + 1          [6]

Looking at [3], we now have:

  F_6(x) = (x^6 - 1) / (F_1(x)*F_2(x)*F_3(x))
         = (x^6 - 1) / ((x - 1)(x + 1)(x^2 + x + 1))
         = x^2 - x + 1          [7]

(Note that PRI(7) is the negative of the coefficient of x, i.e.,
PRI(7) = +1, which confirms what has been said in the previous 
answer.)

These computations require a little more care if the index contains 
repeated prime factors.

The important point is that these operations only involve divisions of
monic polynomials with integer coefficients: they can be done over any
field, and will yield the same result (we did not use any special
property of the field to do the computations).  Strictly speaking,
this is only partially true, since the coefficients of the polynomials
are elements of the base field.  Although [7] is valid over any field,
over the rationals, the coefficients are rational numbers (in fact,
plain integers), whereas, for example, on Z7, they are elements of Z7.
Over Z7, the same polynomial could also be written as:

  F_6(x) = x^2 + 6x + 1   (Over Z7 only!)

I hope this more or less answers your first question (or, at least,
sheds some light on it...).

For the second question, these identities can be proven by some 
elaborate manipulations of formula [1] in my previous answer.  We can 
also try to prove them more directly.

A crucial point is that, if r has order n (in some field), the 
order of r^k is n / gcd(k,n).  In particular, if r is a primitive n-th 
root of unity (a root of F_n(x)), the roots of F_n(x) are those r^k 
such that gcd(k,n) = 1.  The number of such elements is phi(n) 
(Euler's Totient function), and therefore the degree of F_n(x) is
phi(n).  Remember that phi(n) satisfies the following relations:

  phi(mn) = phi(m)phi(n)    if gcd(m,n) = 1
  phi(p^k) = (p-1)*p^(k-1)  if p is prime

Consider first formula (29) in MathWorld's article.  This can be 
written as:

  F_n(x^p) = F_n(x)*F_pn(x)                [8]

with gcd(n,p) = 1.

Notice first that the order of an element is uniquely defined: x 
cannot have both order n and order pn.  This means that the two 
factors of the RHS have no root in common, and are relatively prime.

If r is a root of F_n(x), r is of order n, and r^p is of order
n/gcd(n,p) = n; this means that r^p is a root of F_n(x), and r is a 
root of F_n(x^p).  We can conclude that F_n(x) | F_n(x^p) ("|" means 
"divides").

If r is a root of F_pn(x), r has order pn, and r^p has order
pn / gcd(pn,p) = n.  In this case also, this shows that
F_pn(x) | F_n(x^p).  As F_n and F_pn are relatively prime, we can 
conclude that:

  F_n(x)*F_pn(x) divides F_n(x^p)

Consider now the degrees of the polynomials.  The degree of F_n(x) is 
phi(n), and the degree of F_n(x^p) is p*phi(n).  The degree of F_pn(x) 
is:

  phi(pn) = phi(p)*phi(n)
          = (p-1) * phi(n)

As the degree of a product of polynomials over a field is the sum of 
the degrees of the factors, you can easily verify that both sides of 
[8] have the same degree, which means that both polynomials differ by 
a constant factor.  As these are all monic polynomials (as shown by 
the contruction above), that factor is 1, and we have equality.

(Another possible way of proving [8] would be to show that any root of 
the LHS is a root of one of the factors of the RHS: if r^p has order 
n, then r has order dividing np.  The order of r cannot be p, since 
then we would have r^p = 1, and 1 is not a root of F_n(x).  This still 
requires some elaboration).

Consider now formula (30) of the article.  With the same kind of 
argument as before, we can show that, if r has order np, r^p has order 
np / gcd(p,np) = n, and r is a root of F_n(x^p).  This shows that 
F_np(x) | F_n(x^p).  To compute the degrees of the polynomials, write:

  n = m*p^k

with gcd(m,p) = 1.  We have:

  deg F_n(x) = phi(n) = phi(m*p^k) = phi(m)*phi(p^k)
             = phi(m) * (p-1) * p^(k-1)

  deg F_n(x^p) = p*deg(F_n(x))
               = phi(m) * (p-1) * p^k

  deg F_np(x) = phi(np) = phi(m*p^(k+1))
              = phi(m) * phi(p^(k+1))
              = phi(m) * (p-1) * p^k

and, as you see, the degrees are the same.  As the polynomials are 
monic, they are therefore equal, and this completes the proof.

I hope this makes some sense.  Please write back if you want further 
help.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/20/2005 at 08:00:47
From: Sadanand
Subject: Primitive roots of primes

Hi Doc,

I have followed only a tiny part of your response to the first of my 
doubts.  I am putting down what I have understood. 

I am not sure about the precise definition of a field.  I thought it 
meant a set of elements, finite or infinite, obeying the laws of 
ordinary binary addition and multiplication which should invariably 
give a result which is also an element of the set, and including in 
the set two special elements, namely, an additive identity 0 and a 
multiplicative identity 1.  Does the definition of a field also 
necessitate the existence of inverses of each element w.r.t addition 
and mutiplication, within the set?  For example, in the Boolean field, 
there are no inverses, but all other conditions are satisfied.  Please 
clarify. 

If the existence of multiplicative inverses is not a necessity for the 
definition of a field, can we have a field of monic polynomials with 
integer coefficients as its elements?  The polynomials would obviously 
be equally relevant in the domain of complex numbers, and the domain 
of modulo n integers.  The only thing which characterizes such a monic 
polynomial are its zeros.  So correspondence would be required only 
between the zeros of any particular polynomial in the two domains. 

F1(x) = x – 1            The root of this is 1 in C as well as Z7.
F3(x) = x^2 + x + 1      The roots of this are e^2pi/3, e^4pi/3 in C,
                         and 2, 4 in Z7.
F6(x) = x^2 -x + 1       The roots of this are e^2pi/6, e^10pi/6  in 
                         C, and 3, 5 in Z7.

It is not necessary for a cyclotomic polynomial of order n to have 
roots in every domain Zk.  It is sufficient to consider prime values 
of k such that n is a proper divisor of k – 1.  Thus for F1(x), F2(x), 
F4(x) only the domains Z5 , Z13, Z17 ... are relevant.

F1(x) = x – 1        The root of this is 1 in C as well as in Z5. 
F2(x) = x + 1	     The roots of this are - 1 in C, and 4 in Z5.
F4(x) = x^2 + 1      The roots of this are + i, - i in C, and 2, 3 
                     in Z5.

The corresponding roots in Z13 are 1 for F1(x), 12 for F2(x), and 
5,8 for F4(x).

The corresponding roots in Z17 are 1 for F1(x), 16 for F2(x), and 
4,13 for F17(x).

Am I understanding you correctly?

Sadanand

Date: 06/20/2005 at 11:24:46
From: Doctor Jacques
Subject: Re: Primitive roots of primes

Hi again Sadanand,

A field is essentially a set where the four operations of addition, 
subtraction, multiplication, and division are defined, with the usual 
rules.  In particular, every non-zero element must have a 
multiplicative inverse.

Polynomials by themselves do not constitute a field--if f(x) is a 
polynomial of positive degree, there is no polynomial g(x) such that
f(x)g(x) = 1.

However, if we consider polynomials modulo a fixed irreducible 
polynomial, we can get a field.  For example, with real polynomials 
modulo f(x) = x^2 + 1, we can find an inverse for every non-zero 
polynomial.  (Of course, since we are working modulo f(x), "non-zero" 
means "not divisible by f(x)".)

However, in this case, we cannot simply consider monic polynomials. 
For example, with f(x) as above, we have:

  (x + 1)(x - 1) = x^2 - 1
                 = -2       (mod f(x))

and, therefore:

  (x + 1) * (-(x - 1)/2) = 1  (mod f(x))

which shows that the inverse of the polynomial (x + 1) is -(x - 1)/2; 
that polynomial is not monic.

It is true that, for the purpose of studying primitive roots of a 
prime p, we need only consider the cyclotomic polynomial F_(p-1)(x). 
That polynomial always factors into linear terms over Zp, 
corresponding to the primitive roots modulo p.

However, to study the properties of these polynomials (in particular, 
their second coefficient), we need to consider cyclotomic polynomials 
in a more general context (to be able to use the critical formulas 
(29) and (30) of the article).

In that general case, it is no longer true that a cyclotomic 
polynomial of degree n has n roots--some of the polynomials may be 
irreducible, or factor into terms of degree higher than one, depending 
on the field under consideration.

For example, using the technique I showed you, it is possible to 
verify that:

  F_8(x) = x^4 + 1

That polynomial is irreducible over Q.  However, we have:

  F_8(x) = (x^2 + 3x + 1)(x^2 + 4x + 1)     in Z7

where both factors are irreducible, and

  F_8(x) = (x + 2)(x + 8)(x + 9)(x + 15)    in Z17

(In fact, it can be shown that F_8(x) is never irreducible over any 
finite field.)  As you see, the type of factorization can depend on 
the field, although the polynomial is always the same.

The important point is that these polynomials are always well-defined 
(because it is possible to construct an extension field containing the 
appropriate roots of unity), and that they do not depend on the field 
under consideration (because they can be computed using only 
polynomial divisions between polynomials of the form x^k - 1); in 
addition, they are always monic polynomials with integer coefficients.

This allows us to use formulas (29) and (30) recursively, considering 
cyclotomic polynomials of lower degrees, which do not necessarily 
correspond to F_(p-1) for some prime p; this is why we need to study 
them in the general context.

For example, to compute PRI(7), we need F_6(x).  Of course, we can 
compute it directly (and we did..), but let us use formula (29) with 
n = 3 and p = 2.  This gives:

  F_6(x) = F_3(x^2)/F_3(x)

and, assuming that we know that F_3(x) = x^2 + x + 1, we have:

  F_6(x) = (x^4 + x^2 + 1)/(x^2 + x + 1)
         = x^2 - x + 1

which confirms our previous result.  In this case, we could use the 
fact that the numerator only contains even powers of x, and the fact 
that the second coefficient of the denominator is +1, to deduce that 
the second coefficient of F_6 is -1, and that PRI(7) = +1.

However, in the process, we had to consider F_3(x), which does not 
arise as F_(p-1)(x) for some prime p.  We cannot restrict the study of 
cyclotomic polynomials to that particular case, because we encounter 
other cases as soon as we use formulas (29) and (30).

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/21/2005 at 01:50:42
From: Sadanand
Subject: Primitive roots of primes

Hi Doc,

From your responses, I think there were misconceptions in my mind 
regarding certain basic terms used by you.  The following questions 
are intended to be absolutely certain that I understand these basic 
terms correctly.

1) A field is a set of elements, finite or infinite, amongst which the 
four basic binary arithmetic operations are defined and which always 
yield a result which is an element of the set.  In addition, the set 
must include two special elements, namely the identity elements 0 and 
1 for the operations of addition/subtraction and multiplication/ 
division respectively.  The set must also include the inverses of all 
elements of the set, under the operations of addition and
multiplication.  Is this definition correct?

2) If so, is “Boolean Field” (consisting of just the two elements 0 
and 1) a misnomer?

3) Are the elements of a field necessarily numbers, or can they be 
other mathematical objects like functions, so long as the definition 
of field in (1) above is satisfied?

4) I define a polynomial rational fraction as a polynomial in powers
of x with integer coefficients divided by another similar polynomial.
Can such polynomial rational fractions form a field?

5) What exactly is a monic polynomial?  I had taken it to mean a 
polynomial with a single variable x.  But apparently this is a wrong 
idea.

Sadanand

Date: 06/21/2005 at 03:13:11
From: Doctor Jacques
Subject: Re: Primitive roots of primes

Hi again Sadanand,

Question 1
----------

Your definition is essentially correct (note that 0 does not have a 
multiplicative inverse).  For a more precise definition, see:

  Field Axioms
    http://mathworld.wolfram.com/FieldAxioms.html 

By the way, the MathWorld site is a great resource for definitions.

Question 2
---------
There is indeed a field of two elements, if you define addition and 
multiplication modulo 2.  The term "Boolean field" is a little 
misleading, since there is a concept of "Boolean algebra", where the 
operations are AND and OR, and this is not a field.  These are not the 
same structure: in the field of two elements (GF(2) or Z2), 
multiplication corresponds to the AND operation, but addition is the 
exclusive OR (XOR) operation.

Question 3
----------
The elements of a field need not be numbers, as long as you can define 
two operations (addition and multiplication) that satisfy the field 
axioms (subtraction and division follow).  This is the whole point of 
defining abstract algebraic structures--the properties only depend on 
the axioms, not on particular examples.  The next question gives an 
example of such a field.  Other examples are given by the construction 
I gave you in a previous answer (using polynomials over Zp).  There is 
a field of 4 elements {0, 1, a, b} where the operations are given by:

  + | 0 1 a b        * | 0 1 a b
  --+--------        --+--------
  0 | 0 1 a b        0 | 0 0 0 0
  1 | 1 0 b a        1 | 0 1 a b
  a | a b 0 1        a | 0 a b 1
  b | b a 1 0        b | 0 b 1 a

This field can be created from Z2, by considering polynomials modulo 
the irreducible polynomial f(x) = x^2 + x + 1.  The element a 
corresponds to the equivalence class of the polynomial x.

Question 4
----------
Given a field K (like Q, R, Zp), there is indeed a field of rational 
functions over K, denoted K(x).  The elements are quotients of 
polynomials over K.  You can indeed add, subtract, multiply, and 
divide such functions with the usual rules.

Note that the elements of the field are abstract objects--the 
indeterminate (x for example) is not something that takes a value. 
For example, the inverse of the element x-1 is 1/(x-1)--you do not 
need to worry about x being different from 1, because the element (x-
1) is to be considered as an object of a special type--it is not an 
expression that takes a value depending on x.  Of course, the 0 
element of the field (the constant polynomial 0) does not have an 
inverse.

Question 5
----------
A monic polynomial is a polynomial whose leading coefficient (the 
coefficient of the term of highest degree) is 1.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/21/2005 at 23:54:50
From: Sadanand
Subject: Thank you (Primitive roots of primes)

Hi Doc,							
			
Thanks for your prompt clarifications on questions addressed to you
yesterday.  They have helped clear up the confusion about some basic
terms in my mind.

Sadanand