# Is $x^{17}+x+1$ irreducible over $\mathbb{Q}$? Over $\mathbb{Z}$? Over $\mathbb{F}_2$?

$\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\s}{\sigma}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\F}{\mathbb{F}}$

My assumption: $$P=x^{17}+x+1$$ is a polynomial of degree 17 which is irreducible in $\Q[x], \Z[x]$ and $\F_{2}[x]$

Proof: In $\F_{2}=\{0,1\}$, so only need to check $P(1),P(0)$. Since both are 1, they are not reducible so P is irreducible over $\F_{2}[x]$, since $\F_{2}\cong \Z/2\Z$ it follows with the lemma of gauss that it is also irreducible in $\Z[x]$. Because it is primitive it is also irreducible over $\Q[x]$.

Is this correct?

Finite integral domain is always a field. I think that finiteness means having finite amount of elements. But this does not seem correct, as $\Z$, $\Q$... are also fields but they have infinite amount of elements?

-
Careful! You've only shown that $P$ has no roots in $\mathbb{F}_2[x]$! The polynomial $x^4+x^2+1\in \mathbb{F}_2[x]$ has no roots in $\mathbb{F}_2[x]$, however it's not irreducible since $x^4+x^2+1=(x^2+x+1)^2$. – user5137 Feb 7 '12 at 1:19
Who said anything about $P$ necessarily having quadratic factors? How do you know that $P$ isn't, for example, the product of an eighth degree polynomial and a ninth degree polynomial in $\mathbb{F}_2[x]$? – user5137 Feb 7 '12 at 1:45
No. No, no, no. Consider $f(x)=x^4+x+1\in \mathbb{F}_2[x]$. $f$ has no roots in $\mathbb{F}_2$ (and, incidentally, $gcd(4,1)=1$ which has nothing to do with anything), however, $f(x)$ is reducible in $\mathbb{F}_2[x]$. – user5137 Feb 7 '12 at 1:54
You're correct that if we can write $P(x)=g(x)h(x)$ with $g,h\mathbb{F}_2[x]$ and $deg(g)\geq deg(h)\geq 1$, then the possible pairs $(deg(h),deg(g))$ are $(8,9)$,$(7,10)$,$(6,11)$,$(5,12)$,$(4,13)$,$(3,14)$,$(2,15)$, and $(1,16)$. You've eliminated $(1,16)$ as a possibility by noticing that $P$ has no roots in $\mathbb{F}_2$. What about the other seven cases? – user5137 Feb 7 '12 at 2:01
What does "isomorphy" have to do with anything here? – Arturo Magidin Feb 7 '12 at 3:56

As noted in the comments, your argument for $\mathbb{F}_2$ is incorrect.

Note that if $F$ is a finite field, and $n$ is any positive integers, there exist lots of polynomials with coefficients in $F$ that are (i) irreducible over $F$, (ii) monic; and (iii) of degree $n$. (If $F=\mathbb{F}_q$, and $\alpha$ is a generator of the multiplicative group of the field $\mathbb{F}_{q^n}$, then the monic irreducible polynomial of $\alpha$ over $\mathbb{F}_q$ is of degree $n$). In particular, you can find lots of polynomials of degree 17 over $\mathbb{F}_2$ that are reducible but have no roots: just write 17 as a sum of positive integers greater than 1, and find polynomials of appropriate degrees. E.g., there are degree 17 polynomials with coefficients in $\mathbb{F}_2$ that are products of irreducibles of degree 5, 4, 3, 3, and 2. The fact that 17 is odd is irrelevant; you can even find a reducible polynomial of degree 17 all of whose irreducible factors are of odd degree (a product of two degree 5 and one degree 7 irreducible, for example).

You could check to see whether your polynomial has a factor of degree at most $8$, by running through the irreducibles of degree 2 through 8. But you'd have to go through all of them. But before you start, you might want to know how many there are. The number of monic irreducible polynomials of degree $n$ over the field $\mathbb{F}_q$ is $$\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)q^d,$$ where $\mu$ is the Möbius function. (A formula of Gauss; there is a combinatorial proof in a recent Mathematics Magazine paper.)

For instance, the number of degree 7 irreducibles over $\mathbb{F}_2$ is $$\frac{1}{7}\left(2^7-2\right) = 18$$ and the number of irreducibles of degree 8 is $$\frac{1}{8}(2^8 - 2^4) = 30.$$ There are better ways to test irreducibility over finite fields. You may want to consult Wikipedia.

Because the polynomial is primitive, by Gauss's Lemma, irreducibility over $\mathbb{Q}$ is equivalent to irreducibility over $\mathbb{Z}$. However, primitivity by itself does not prove that the polynomial is irreducible over either! $x^2+2x+1$ is primitive (every monic polynomial is necessarily primitive over $\mathbb{Z}$), but is certainly not irreducible. Of course, if a polynomial is not primitive then it will factor in $\mathbb{Z}[x]$, but one of those factors will be constant; we don't usually refer to those when talking about "irreducibility" of a polynomial (though we do when discussing the fact that $\mathbb{Z}[x]$ is a Unique Factorization Domain).

If you could prove the polynomial is irreducible over $\mathbb{F}_2$, then this would imply irreducibility over $\mathbb{Z}$ (any factorization over $\mathbb{Z}$ gives a factorization over $\mathbb{F}_2$ by modular reduction). But the polynomial may be reducible over $\mathbb{F}_2$ yet irreducible over $\mathbb{Z}$.

(As it happens, the polynomial is reducible over $\mathbb{Z}$, with a factor of degree 2...)

As to your second query: An integral domain that is finite (as a set) must be a field. It is not the same to say "every element is finite" than to say "the set is finite." Every element of the integers is a finite number, but the set of integers is infinite. The theorem does not apply to $\mathbb{Z}$ or to $\mathbb{Q}$ because, although they are integral domains, they are infinite (they have infinitely many elements). Note that $\mathbb{Z}$ is an integral domain that is not a field. And the theorem doesn't say anything about infinite integral domains; they can be fields or not. The point of the theorem is that if $D$ is an integral domain, and $D$ is finite, then $D$ will necessarily be a field; if $D$ is not an integral domain, or not finite, then the result expresses absolutely nothing about $D$.

-
Arturo Magidin, Thank you for your explanation! Is there a way to construct irreducible polynomials directly?? – VVV Feb 7 '12 at 4:38
@VVV: Recursively, sure; directly? I don't know any, but that doesn't mean none exist. – Arturo Magidin Feb 7 '12 at 5:30
By recursively you mean you would write up all polynomials of degree 17 in GF(2) and then check which ones are irreducible by dividing them by the ones of smaller degree (2 to 8)?? – VVV Feb 7 '12 at 5:58
@VVV: I mean generate the ones of degree 2; then those of degree 3; then use those to generate those of degree 4, etc. – Arturo Magidin Feb 7 '12 at 15:02
A computationally reasonable first pass is to compute $GCD(f, x^{p^d}-x)$. Every irreducible polynomial of degree $d$ over $\mathbb{F}_p$ divides $x^{p^d}-x$, so this can rule out a lot of $d$'s immediately. (That's how I found the factor $x^2+x+1$ below.) If this doesn't immediately answer the question, see Arturo's Wikipedia link. – David Speyer Feb 7 '12 at 16:01

In fact, your polynomial is not irreducible over $\mathbb{F}_2$ or $\mathbb{Z}$: It is divisible by $x^2+x+1$. The easiest way to see this is that $x^2+x+1$ divides $x^3-1$, and hence divides $x^{17}-x^2$. Your polynomial is $(x^{17}-x^2) + (x^2+x+1)$.

I found this in a sort of roundabout way, but it turns out that WolframAlpha will do this for you.

-
+1 I should have realized that this factor works also over $\mathbf{Z}$. Very well done. – Jyrki Lahtonen Feb 7 '12 at 20:44

The following is the easiest argument that I could come up with showing that $p(x)=x^{17}+x+1$ cannot be irreducible in the ring $F_2[x]$.

Compute first $$(x+1)p(x)=(x+1)x^{17}+(x+1)^2=x^{18}+x^{17}+x^2+1=(x^{18}+1)+(x^{17}+x^2).$$ Then we recall the factorization of $x^3+1=x^3-1=(x-1)(x^2+x+1)=(x+1)(x^2+x+1).$ I next claim that the above product $(x+1)p(x)$ is actually divisible $x^3+1$. This follows from my grouping in the last form. We have $$x^{18}+1=(x^3)^6+1\qquad\text{and}\qquad x^{17}+x^2=x^2\left((x^3)^5+1\right).$$ By the hopefully familiar fact that $a^n-1$ is always divisible by $a-1$ for any positive integer $n$, we see that both these polynomials are divisible by $x^3+1$, and hence so is their sum.

Because $(x+1)p(x)$ is divisible by $(x+1)(x^2+x+1)$, unique factorization implies that $p(x)$ is divisible by $x^2+x+1$.

-