Irreducible Polynomial g = X^4 + X + 1 over F2

[aadams]

I am really struggling on the following Algebra question:

Consider the Irreducible Polynomial g = X^4 + X + 1 over 𝔽2 and let E be the extension of 𝔽2 = {0,1} with root α of g.

(a) How many elements does E have?

(b) Is every non-zero element of E of the form α^n with n ϵ N (natural numbers)?

(c) Find all roots of g in E expressed in the form ν + µα + λα^2 + γα^3.

(d) Find the roots of X^2 + X + 1 in E.

(e) Find a subfield of order 4 in E.

(f) Could E have a subfield of order 8.

(g) Could X^3 + X + 1 have a root in E?

I have tried part (a) and I think there are 16 elements in E, as I think that E = 𝔽[X]/g𝔽[X] = 𝔽[X]/I where I is the ideal of 𝔽[X]. and so E = {f + I | f ϵ 𝔽[X]}

I then proceeded to carry out long division of f by g and ended up with: E = {ν + µα + λα^2 + γα^3 |γ,λ,µ,ν ϵ {0,1}}

by substituting in 0 and 1 for the values above, I end up with 16 elements of E. I am not sure if this is correct as it seems a bit long winded for part (a) as it is only worth 2 marks.

I would appreciate help with any of the question! Thanks!

 

[Euge]

Welcome, aadams! (Wave)

Your answer to (a) looks fine. To answer part (b), you can compute the powers $\alpha^n$ for $n = 1,2,\ldots, 15$ using the relation $\alpha^4 = \alpha + 1$. Note that more generally, the multiplicative group of a finite field is cyclic. For part (c), consider $\alpha, \alpha^2, 1 + \alpha$, and $1 + \alpha^2$. In (d), you want to find two elements $y$ such that $y^2 = y + 1$; look at the powers of $\alpha$ that are of the form $\beta + 1$. Try these out first, then we can discuss (e), (f), and (g).

 

[aadams]

Thank you very much for your help!

I'm still a bit confused on part (b) - I can see that α^4=α+1 and how this helps to write elements as α^n.
I'm not sure how I could write elements such as α^2 + 1 and α^2+α+1 as α^n?? Also with other elements α^3+α, α^3+1, α^3+α^2+α, α^3+α+1 and α^3+α^2+α+1.

Thanks again!

 

[Euge]

Thank you very much for your help!

I'm still a bit confused on part (b) - I can see that α^4=α+1 and how this helps to write elements as α^n.
I'm not sure how I could write elements such as α^2 + 1 and α^2+α+1 as α^n?? Also with other elements α^3+α, α^3+1, α^3+α^2+α, α^3+α+1 and α^3+α^2+α+1.

Thanks again!

You can start with $\alpha^4 = \alpha + 1$, multiply by $\alpha$ and reduce (if necessary). Then repeat the procedure. If in case you don't want to list them all out, the following argument can be used. The multiplicative group of $E$ is cyclic of order $15$, so the multiplicative order of $\alpha$ has to divide $15$. Since neither $\alpha^3$ nor $\alpha^5$ is the identity, $\alpha$ must generate the group. Hence, every nonzero element of $E$ is of the form $\alpha^n$ for some natural number $n$.