Irreducible polynomials over $\mathbb{Z}_2[x]$

Question

Prove that the polynomial $1+x+..+x^m$ is irreducible over $\mathbb{Z}_2$ if and only if $m+1$ is a prime number and 2 is a primitive root in $\mathbb{Z}_{m+1}$

Is there any proof without using cyclotomic field?

Answer 1

Let us denote $$f_k(x):=1+x+x^2+\cdots+x^{k-1}=\frac{x^k-1}{x-1},\qquad(*)$$ $k>2$. First an easy observation.

Claim 1. If $k$ is not a prime number, then $f_k(x)$ is reducible.

Proof. Assume that $k=ab$ with $a,b>1$. As $f_k(x)$ has $k$ terms we can split them into $b$ groups of $a$ consecutive terms and find that $$ f_k(x)=f_a(x)(1+x^a+x^{2a}+\cdots+x^{(b-1)a})=f_a(x)f_b(x^a). $$ QED.

Observe that Claim 1 holds in all fields - irrespective of characteristic. In particular a necessary condition for $f_{m+1}(x)$ to be irreducible is that $m+1$ is a prime number.

From this point on let's concentrate on $\Bbb{Z}_2[x]$. Claim 1 says that unless $m+1=p$ is a prime number, then $f_p(x)$ is reducible, so assume that this is the case. Let $\alpha$ be a zero of $f_p(x)$ in some extension field $K=\Bbb{Z}_2[\alpha]$ of the field $\Bbb{Z}_2$. From $(*)$ we see that $\alpha$ must be a primitive root of unity of order $p$. Anyway, $\alpha$ is algebraic over $\Bbb{Z}_2$, so it has a minimal polynomial $m(x)\in\Bbb{Z}_2[x]$.

[What follows will be overkill, if you are familiar with Galois theory, or may have a hazy step, if you are not at all familiar with it. I'm not sure what's the best level of detail here.]

Next we recall the Frobenius automorphism $F:K\to K, F(z)=z^2$. It is a $\Bbb{Z}_2$-automorphism of $K$, so if $\beta\in K$ is a zero of a polynomial $r(x)\in\Bbb{Z}_2[x]$, then so is $F(\beta)$. Applying this to the case $\beta=\alpha$, $r(x)=m(x)$, we see that the elements $$ \alpha_i=F^i(\alpha)=\alpha^{2^i}, i\in\Bbb{N},\qquad(**) $$ are all zeros of $m(x)$. How many distinct elements $\alpha_i$ of this form are there in $K$? Recall that we also have $\alpha^p=1$ and $p$ is the smallest positive exponent with this property. Let $\ell$ be the order of $2$ in the group $\Bbb{Z}_p^*$. This means that $$ 2^\ell\equiv1\pmod p, $$ or that $2^\ell=1+tp$ for some integer $t$, and $\ell$ is the smallest positive integer with this property. Therefore $$ \alpha_\ell=\alpha^{2^\ell}=\alpha^{1+tp}=\alpha\cdot(\alpha^p)^t=\alpha=\alpha_0. $$ By applying $F$ to this we see that $\alpha_{\ell+1}=\alpha_1$, $\alpha_{\ell+2}=\alpha_2$ et cetera. In other words, there are at most $\ell$ elements $\alpha_i$ in $K$. We easily that actually there are exactly $\ell$ elements of this form. For if $\alpha_i=\alpha_j, 0\le i<j<\ell$, then $\alpha^{2^i}=\alpha^{2^j}$ implying that $1=\alpha^{2^j-2^i}$. As $\alpha$ is of order $p$ we must have $p\mid (2^j-2^i)=2^i(2^{j-i}-1)$. As $p$ is odd, this implies that $2^{j-i}\equiv1\pmod p$ contradicting the minimality of $\ell$.

A missing key observation is that the elements $\alpha_0,\alpha_1,\ldots,\alpha_{\ell-1}$ are all the zeros of $m(x)$. To see this consider that polynomial $$ r(x)=(x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{2^{\ell-1}}) =\sum_{i=0}^{\ell}r_ix^i\in K[x]. $$ Let's apply $F$ to the polynomial $r(x)$. Because $F$ permutes the factors of $r(x)$ we see that the polynomial $r(x)$ does not change at all! In other words, all the coefficients $r_i$ are fixed by $F$, $F(r_i)=r_i$ for all $i$. So $r_i^2=r_i$ implying that $r_i\in\{0,1\}$. Hence $r(x)\in \Bbb{Z}_2[x]$, and $r(x)$ must be a factor of $m(x)$. But, we saw that all the (simple) zeros of $r(x)$ are also zeros of $m(x)$, so we also have $r(x)\mid m(x)$. Therefore we have proved:

Claim 2. If $\ell=\operatorname{ord}_{\Bbb{Z}_p^*}(2)$, then the minimal polynomial of a root of unity of order $p$ over $\Bbb{Z}_2$ has degree $\ell$.

The rest is easy. For $f_p(x)$ to be irreducible it has to be equal to the minimal polynomial $m(x)$. This happens if and only if $\ell=\deg f_p=p-1$. In other words, $f_p(x)$ is irreducible over $\Bbb{Z}_2$ if and only if $2$ is a primitive root modulo $p$.