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} + 5x + 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 ϕ(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].

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

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

Ans.

(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, α, β} where both α and β are roots of the polynomial t^{2} +t+1. Moreover, β = α + 1 and α = β + 1, and β = α^{2} and α = β^{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 ϕ(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 αx. Since x has order 7 and α has order 3, αx has order 21. Now look at the polynomial αx + 1. In computing its powers as elements of K, bear in mind that α^{2} = α + 1 and x^{3} = x + 1. If γ denotes the congruence class of αx + 1 mod f(x), as one computes the first so many powers, one finds that γ^{9} = x^{2} + x + 1, and this is the smallest positive power of γ that is in the subfield E. By the division algorithm (for integers) only the powers of γ that are 0 mod 9 can fall in E. Since x^{2} + x + 1 has order 7, as noted above, we see that γ has order 63 and is, therefore, primitive.