Let c be the smallest positive primitive root modulo p.
|
Let n be the order of the congruence class of the polynomial f(x) modulo the polynomial m(x) over the field F_{p}.
|
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.
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.
F_{4} is defined to be the field F_{2}[t]/(t^{2} + t + 1)F_{2}[t].
Explain why the polynomial f(x) = x^{3} + x + 1 is irreducible over F_{4}.
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, 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.