Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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)$.

share|improve this answer
    
$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
1  
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
    
@JyrkiLahtonen, thank You for answer! But I have one more. Is it possible to determine the root order of any polynomial? –  Sergey Apr 7 '12 at 8:55
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.