Solutions to Written Assignment No. 5

Let c be the smallest positive primitive root modulo p.

prime p primitive root c 23 5 53 2 71 7 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 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.