Classical Algebra (Math 326)
Solutions to Written Assignment No. 5

due Friday, May 11, 2001

  1. Let c be the smallest positive primitive root modulo p.

    prime p primitive root c

    23 5
    53 2
    71 7

  2. Let n be the order of the congruence class of the polynomial f(x) modulo the polynomial m(x) over the field F_{p}.

    f(x) modulus m(x) prime p order n

    x x^{2} + 1 p = 5 4
    x x^{2} - x + 1 p = 5 6
    x - 2 x^{2} + 5 x + 1 p = 7 14
    x + 1 x^{3} - x^{2} + 1 p = 3 13

  3. Show that over any field F the polynomial x and the polynomial f(x) are coprime polynomials if and only if f(0) <> 0.

    Ans. Inasmuch as x is irreducible (since of degree 1), x and f(x) have a non-trivial common factor if and only if the former divides the latter. By the division algorithm f(x) = q(x) x + r, where r is a constant, and so f(0) is the remainder when f(x) is divided by x.

  4. Find a polynomial f(t) in F_{5}[t] whose congruence class modulo m(t) is a primitive element for the field F_{5}[t]/m(t) F_{5}[t] when m(t) = t^{2} - t + 1.

    Ans. Since m(t) is irreducible over F_{5}, the ring of congruence class modulo m(t) is a field, and, therefore, it has 24 units, and the number of primitive elements is phi(24) = 8. They are the polynomials c(t + 1), c(t - 2) where c is one of {+/-}1, {+/-}2.

  5. F_{4} is defined to be the field F_{2}[t]/(t^{2} + t + 1)F_{2}[t].

    1. Explain why the polynomial f(x) = x^{3} + x + 1 is irreducible over F_{4}.

    2. Find a primitive element for the field K = F_{4}[x]/f(x)F_{4}[x].

    (a) A cubic polynomial is irreducible over F_{4} if and only if it has no root in F_{4}. Now F_{4} consists of the elements {0, 1, alpha, beta} where both alpha and beta are roots of the polynomial t^{2} + t + 1. Moreover, beta = alpha + 1 and alpha = beta + 1, and beta = alpha^{2} and alpha = beta^{2}. It is easy to see that f(x) has no root in F_{4}.

    (b) -- difficult The ring K is therefore a field of 4^{3} = 64 elements, and the number of its primitive elements is phi(64) = 36. Since f(x) has coefficients not just in F_{4} but, in fact, in F_{2}, the congruence class mod f(x) of any polynomial with coefficients in F_{2} is an element of the subfield E = F_{2}[x]/f(x)F_{2}[x], which has 8 elements. Since the number of units in E is 7, which is a prime, any unit in E other than 1 is a primitive element of E. Hence, in particular, the congruence class of x modulo f(x) has order 7.

    Since we are forced to look at polynomials whose coefficients are in F_{4} but not all in F_{2} in order to find congruence classes of order larger than 7, we try the polynomial alpha x. Since x has order 7 and alpha has order 3, alpha x has order 21. Now look at the polynomial alpha x + 1. In computing its powers as elements of K, bear in mind that alpha^{2} = alpha + 1 and x^{3} = x + 1. If gamma denotes the congruence class of alpha x + 1 mod f(x), as one computes the first so many powers, one finds that gamma^{9} = x^{2} + x + 1, and this is the smallest positive power of gamma that is in the subfield E. By the division algorithm (for integers) only the powers of gamma that are 0 mod 9 can fall in E. Since x^{2} + x + 1 has order 7, as noted above, we see that gamma has order 63 and is, therefore, primitive.