# Proof for minimal polynomial $\mathbb{F}_q$

Show that each monic irreducible polynomial of $\mathbb{F}_q[x]$ of degree $m$ is the minimal polynomial of some element of $\mathbb{F}_{q^m}$ with respect to $\mathbb{F}_q$ .

Using theorem, find all the irreducible polynomials of degree 4 over F2. (Let α be a root of 1 + x^3 + x^4 ∈ F2[x].)

• The part after "I messed it up" is not clear. What theorem do you mean? Where is the connection to the first part? – azimut Nov 3 '13 at 17:24
• I second azimut's query. His +1 answer takes care of the question in the first paragraph. – Jyrki Lahtonen Nov 3 '13 at 17:26
• To prove that a quartic is irreducible you need to check that it doesn't have linear or irreducible quadratic divisors. A polynomial has a linear factor, iff it has a zero in the base field (here $\Bbb{F}_2$). There is only one irreducible quadratic polynomial in $\Bbb{F}_2[x]$. If you are asked to prove the irreducibility of $x^4+x^3+1$, then you have surely been given that irreducible quadratic in class :-) Hint: it is the only quadratic that does not have zeros in $\Bbb{F}_2$. – Jyrki Lahtonen Nov 3 '13 at 17:31
• i know what you say. but i must show this using the current theorem. so i did not get, exactly. – spectralmath Nov 3 '13 at 17:32
• to azimut with respects =) Using theorem, find all the irreducible polynomials of degree 4 over F2. (Let α be a root of 1 + x^3 + x^4 ∈ F2[x].) – spectralmath Nov 3 '13 at 17:35

Adding my bit with a view of covering the possibility (somewhat implied by OP's comments) that the task really is to find all the irreducible quartic polynomials over $\Bbb{F}_2$ using the theorem that they must all be factors of $p(x)=x^{16}-x$.

The given minimal polynomial of $\alpha$, $f_1(x)=x^4+x^3+1$ is obviously one of those. A useful trick for finding another one is to go to the so called reciprocal polynomial, i.e. $$f_2(x)=x^4f_1(\frac1x)=x^4(\frac1{x^4}+\frac1{x^3}+1)=1+x+x^4.$$ We immediately see that $$f_2(\frac1\alpha)=\alpha^4f_1(\alpha)=0,$$ so $f_2(x)$ is a multiple of the minimal polynomial of $1/\alpha$. As the elements $\alpha$ and $1/\alpha$ generate the same extension field, their respective minimal polynomials must be of the same degree. Therefore $f_2(x)$ is the minimal polynomial of $1/\alpha$ and is, thus also irreducible.

Let's take stock. We know that in addition to $f_1(x)$ and $f_2(x)$ the polynomial $p(x)$ is divisible by $q(x)=x^4-x$ (if you don't know how to deduce this from properties of finite fields, then you can just calculate that $q(x)^4+q(x)=p(x)$. Thus we know that $p(x)$ factors like $$p(x)=q(x) f_1(x) f_2(x) r(x),$$ where $r(x)$ is some yet unknown factor. We can partially factor $p(x)$ directly as follows: $$p(x)=x(x^{15}-1)=x(x^5-1)(x^{10}+x^5+1)=x(x-1)(x^4+x^3+x^2+x+1)(x^{10}+x^5+1),$$ and $q(x)$ as follows: $$q(x)=x(x^3-1)=x(x-1)(x^2+x+1),$$ where that last quadratic factor is irreducible.

I leave it as an exercise for you to check that $$(x^2+x+1)f_1(x)f_2(x)=x^{10}+x^5+1.$$ Putting all this together gives us that the mystery factor $r(x)=f_3(x)=x^4+x^3+x^2+x+1$. I next claim that $f_3(x)$ is irreducible. As it has no zeros in $\Bbb{F}_2$ it has no linear factors in $\Bbb{F}_2[x]$. It cannot be a product of two distinct quadratics, because then it should be a factor of $q(x)$. It cannot be the square of a quadratic, because then its zeros would not be simple, but $f_3(x)$ is a factor of $p(x)$ that has 16 distinct zeros.

Thus the list $f_1(x), f_2(x), f_3(x)$ is a complete list of irreducible quartics in $\Bbb{F}_2[x].$

Yet another way of deducing the irreducibility of $f_3(x)$ is to observe that $f_3(x)\mid x^5-1$, so its zeros are fifth roots of unity. If you are familiar with the cyclicity of the multiplicative groups of finite fields, then you can immediately check that $\Bbb{F}_{16}$ has no proper subfields containing primitive fifth roots of unity. Therefore the minimal polynomial of a fifth root of unity over $\Bbb{F}_2$ must have degree four, i.e. equal to $f_3(x)$.

Observe that $f_3(x)$ is its own reciprocal polynomial. Polynomials with this property are called palindromic because you can equally well read their sequence of coefficients backwards. Therefore our first trick won't give us a fourth irreducible quartic.

• Thank you very much. really I appreciate you Jyrki Lahtonen . – spectralmath Nov 3 '13 at 19:26

This question is a bit strange, since the real work is in showing that all fields of order $q^m$ are isomorphic. If $\def\F{\Bbb F}P\in\F_q[X]$ is irreducible with $\deg P=m$, then $K=\F_q[X]/(P)$ is a field with $q^m$ elements in which the image $\bar X$ of $X$ has minimal polynomial$~P$ over$~\F_q$. If you know that necessarily $K\cong\F_{q^m}$, just choose an isomorphism and let $\alpha\in\F_{q^m}$ be the element corresponding to$~\bar X$ under the isomorphism.

There is a slight subtlety in that here you view $\F_q$ as a subfield of $\F_{q_m}$ by restriction (from $K$ to $\F_q$) of the chosen isomorphism. If you had already an embedding $\F_q\hookrightarrow\F_{q_m}$ when $\F_{q^m}$ was first given to you, then you must make sure to match that embedding, which plays a vital role when you talk about minimal polynomials over $\F_q$ of elements of $\F_{q^m}$. Fortunately this can always be done: every finite field is normal over the prime field $\F_p$, so there is a surjective morphism $\def\Gal{\operatorname{Gal}}\Gal(\F_{q^m}/\F_p)\to\Gal(\F_q/\F_p)$ that can be used to adjust the embedding to what is needed by applying an automorphism of $\F_{q^m}$.

Let $f$ be a monic irreducible polynomial over $\mathbb F_q$ of degree $m$ and $F$ be an algebraic closure of $\mathbb F_q$. $f$ has a zero $\alpha$ in $F$. So $f$ is the minimal polynomial of $\alpha$ over $\mathbb F_q$ and $$[\mathbb F_q(\alpha) : \mathbb F_q] = \deg(f) = m,$$ so $\lvert \mathbb F_q(\alpha)\rvert = q^m$. Since all finite fields of the same order are isomorphic, $\mathbb F_q(\alpha) \cong \mathbb F_{q^m}$. Thus, there is an element $a\in \mathbb F_{q^m}$ such that $f$ is its minimal polynomial.

For the subtle point why it is possible to find $a$ such that the minimal polynomial $f$ is not "twisted" by the isomorphism $\mathbb F_q(\alpha) \to \mathbb F_{q^m}$, see the discussion below and in particular the explanation of Marc van Leeuven.

• so α^4=α^3+1 is my primitive element. so 1+x^3+x^4 is irreducible over F2 am i right? – spectralmath Nov 3 '13 at 17:20
• I answered the first part of your question: "Show that each monic irreducible polynomial of $\mathbb F_q[x]$ of degree $m$ is the minimal polynomial of some element of $\mathbb F_{q^m}$ with respect to $\mathbb F_q$. – azimut Nov 3 '13 at 17:23
• I am not sure that the reasoning is correct (or, at least, complete): Say you have the isomorphism $\varphi:\mathbb{F}_q(\alpha)\rightarrow \mathbb{F}_{q^m}$. Then it is clear that $\varphi(\alpha)$ is a root of $\overline{\varphi}(f),$ where $\overline{\varphi}$ is the isomorphism $\varphi$ extended to the ring $\mathbb{F}_q[x]$ in the obvious way. But how would you ensure that it is a root of $f$ as well? For this to work, you need $\varphi$ to be $\mathbb{F}_q$-isomorphism. – Pavel Čoupek Nov 3 '13 at 17:50
• @PavelC: In the moment where you define $\alpha$, you know that $f$ is its minimal polynomial over $\mathbb F_q$. I've changed the order of the arguments in my answer to make this clear. – azimut Nov 3 '13 at 18:10
• I think this still does not solve it (say you have $\mathbb{R}\subseteq \mathbb{C}$ and an automorphism of $\mathbb{C}$ which sends an element $\alpha \in \mathbb{C}\setminus \mathbb{R}$ to something other than its conjugate. Then the minimal polynomial of the element changes). – Pavel Čoupek Nov 3 '13 at 18:25