# Why $x^4+x^3+x^2+x+1$ has root order 1 or 5 in $GF(2)$?

Why $x^4+x^3+x^2+x+1$ has root order 1 or 5 in $GF(2)$?

For example: $P(x)=x^4+x^3+x^2+x+1$ is irreducible over $GF(2)$. Note, that $(x^5-1)=(x-1)(x^4+x^3+x^2+x+1)$. Those, any root of $P(x)=0$ has order 5 or 1.

Why?

-
It may mean order as an element of the multiplicative group of an appropriate extension field. –  André Nicolas Apr 6 '12 at 18:00
If $x^4+x^3+x^2+x+1=0$, then $x^5-1=0$ or $x^5=1$. So the least $n$ with $x^n=1$ is a factor of $5$, and thus either $n=1$ or $n=5$. –  GEdgar Apr 6 '12 at 18:30

Here the order of a root $\alpha$ clearly means the order of $\alpha$ in multiplicative group $GF(2)[\alpha]^*$. IOW, the order of $\alpha$ is the smallest positive integer $m$ such that $\alpha^m=1$. So let us assume that $P(\alpha)=0$, where $\alpha$ belongs to some extension field $GF(q)$, $q$ a power of two.
The factorization that you gave $$x^5-1=(x-1)P(x)$$ shows that $$\alpha^5-1=(\alpha-1)P(\alpha)=(\alpha-1)\cdot0=0.$$ Therefore $\alpha^5=1$. From the basic theory of cyclic groups we know that the order of $\alpha$ must then be a factor of five, i.e. either five or one. The latter possibility is easy to exclude. If $\alpha$ were of order one, then $1=\alpha^1=\alpha$. But $P(1)=5=1\neq0$, so $1$ is not a zero of $P(x)$.
$GF(16)$ is the smallest extension field $GF(q)$ of $GF(2)$ with the property that $5\mid(q-1)$. It follows relatively easily that $P(x)$ has four distint zeros in the field $GF(16)$. –  Jyrki Lahtonen Apr 6 '12 at 18:08
And the presence of $GF(2)$ in the question is a red herring. The conclusion (that the order of a root is either $1$ or $5$) is true in whatever ring $x$ can be evaluated to to make $P(x)=0$. –  Lubin Apr 6 '12 at 18:19
@Lubin, you are, of course, correct. The question is more meaningful in a finite field though. Mostly because in a finite field all non-zero elements have a finite order. With the present polynomial it doesn't matter, because $P(x)$ is the fifth cyclotomic polynomial. –  Jyrki Lahtonen Apr 6 '12 at 18:30
@Sergey, sorry about missing that last question. It is possible, but computationally somewhat taxing. For example, if you know that $P(x)$ is irreducible, then the order will be a factor of $2^{\deg P(x)}-1$, but will not be a factor of any smaller number of the form $2^k-1$. That still leaves you many cases, but does cut down the work. If $P(x)$ is not irreducible, then the question becomes a bit ill-defined in the sense that the answer typically depends on the choice of the root $\alpha$. We should then really replace $P(x)$ with the minimal polynomial of $\alpha$. –  Jyrki Lahtonen Apr 11 '12 at 20:11