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

### Primitive Roots of Primes

```Date: 06/05/2005 at 01:10:47
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

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,

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
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.

```

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

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

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
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?

```

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

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
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.

```

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

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
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.

```
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