# Is this an irreducible polynomial?

I have this polynomial:

$x^8+x^4+x^3+x+1$

and I would like to know if it is irreducible over $\mathbb{F}_q$ with $q=2^8$. My book gives me it is irreducible but matlab says it is not irreducible.

-

This is a polynomial over which ring? It is (certainly!) reducible as a polynomial over $\mathbb C$, for example. – Henning Makholm Dec 2 '12 at 23:34
I edited the post... I mean over Galois Field $GF(2^8)$ – Mazzy Dec 2 '12 at 23:35
Reducibility depends on the field. Every polynomial with real coefficients can be written as a product of terms of the type $(x^2 + b x + c)$ and other terms of the type $(x + c)$ with real numbers $b,c$ and perhaps an overall multiplier $a.$ Thi, of course, is just the statement that roots occur in complex conjugate pairs. – Will Jagy Dec 2 '12 at 23:36
@WillJagy I edited the post. I mean galois finite field – Mazzy Dec 2 '12 at 23:38

## 2 Answers

Theorem. Let $P$ be any polynomial of degree $k\ge 2$ with coefficients in $\mathbb F_p$. Then $P$ is reducible over $\mathrm{GF}(p^k)$.

Proof. If $P$ is reducible over $\mathbb F_p$, then the same factorization works over $\mathrm{GF}(p^k)$. So assume $P$ is irreducible over $\mathbb F_p$. Then $\mathbb F_p[X]/(P)$ is isomorphic to $\mathrm{GF}(p^k)$, so the image of $X$ under this isomorphism is a root of $P$. Therefore $P$ has a linear factor in $\mathrm{GF}(p^k)[X]$.

-
So you want say me that my polynomial is reducible. right? – Mazzy Dec 2 '12 at 23:49
according what you say instead, $1+x^2+x^3+x^4+x^8$ is reducible over GF(2^8), right? – Mazzy Dec 2 '12 at 23:52
@Mazzy: Um, yes. – Henning Makholm Dec 2 '12 at 23:53
So why matlab says me that the last one is a primitive polynomial? – Mazzy Dec 2 '12 at 23:54

1
@Mazzy: Beats me. My immediate guess would be that it's answering a different question than you think it is (such as whether the polynomial is irreducible over $\mathbb F_2$). – Henning Makholm Dec 2 '12 at 23:59

If a polynomial of degree 8 over $\mathbb{F}_q$ is irreducible over the finite field $\mathbb{F}_q$, then its splitting field is $\mathbb{F}_{q^8}$, and is thus reducible over $\mathbb{F}_{q^8}$. If a polynomial of degree 8 over $\mathbb{F}_q$ is reducible over the finite field $\mathbb{F}_q$, then it remains reducible over $\mathbb{F}_{q^8}$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9215883016586304, "perplexity_flag": "head"}