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