Determine every degree 4 primitive polynomial in $GF(2)[x]$ Determine, showing all reasoning, every degree 4 primitive polynomial in $GF(2)[x]$.
I think $x^4+x+1$ might be one but I do not know how to show it, could anyone explain?
Also after this, how would I know that I have found every one?
 A: To show that $f = x^{4} + x + 1$ is primitive, first of all check it is irreducible. (You may skip this, see below.)
You will want to show that 


*

*it has no roots in $GF(2)$ (so it has no factor of degree $1$ in $GF(2)[x]$), and then 

*you will have to check that it has no irreducible factor of degree $2$ - this will be easy, as there are not many such polynomials.


Then check it is primitive, by computing the multiplicative period of $x$ modulo $f$. This second check will also prove independently that $f$ is irreducible, if you know the argument.
There is another primitive polynomial, which is $x^{4}(f(x^{-1}))$.
To see that there no others, you may check that the multiplicative group of $GF(2^{4})$, which is cyclic of order $2^{4} - 1 = 15$, has exactly $\phi(15) = 2 \cdot 4 = 8$ generators. Hence they are all covered by the two polynomials.
A: The product of every monic irreducible polynomial over $\mathbb{F}_2$ with degree $1,2$ or $4$ is given by $x^{2^4}-x$ and the product of every monic irreducible polynomial with degree $1,2$ is given by $x^{2^2}-x$. It follows that the product of every monic irreducible polynomial over $\mathbb{F}_2$ with degree four is given by:
$$\frac{x^{16}-x}{x^4-x} = \left(1+x+x^2+x^3+x^4\right) \left(1-x+x^3-x^4+x^5-x^7+x^8\right) $$
and the only monic irreducible polynomials with degree $4$ are
$$ 1+x+x^2+x^3+x^4,\quad 1+x^3+x^4,\quad 1+x+x^4.$$
