In "Shu Lin, Daniel J. Costello-Error Control Coding (2nd Edition), Prentice Hall 2004" it is given that in $GF(2)$, if $f(x)$ is an irreducible polynomial of degree $m$ it divides $x^n+1$ where $n = 2^m -1$. And as per mathematica documentation, $x$ is an irreducible polynomial, here is the conflict. $x$ does not divide $x+1$. Also $x$ is declared non-primitive! Just want clarification. Wolfram documentation i.e mathematica documentation

  • $\begingroup$ Your definition of $m$ does not make sense: in general, $m \neq 2^m-1$. $\endgroup$
    – MBaz
    Mar 23, 2016 at 15:06
  • $\begingroup$ @MBaz:Thanks for pointing out the error in typing. I corrected it. I meant actually $n$ = $2^m$ -1 $\endgroup$ Mar 23, 2016 at 17:06

1 Answer 1


From the Wikipedia page irreducible polynomials: "a non-constant polynomial $f$ in $F[x]$ is said to be irreducible over [the field] $F$ if it is not the product of two polynomials of positive degree."

From this definition, it should be clear that $x$ cannot be viewed as the product of two polynomials of positive degree. Take one polynomial to be $x$ then there is no other polynomial (with degree greater than zero). Irreducible polynomials act like prime numbers in the field in that other polynomials can be factored into (powers of) the irreducible polynomials.

A primitive polynomial has a different definition. "In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field $GF(p^m)$." Notice that irreducible polynomials can be defined over any field, but primitive polynomials only apply to the extension of a finite field. These polynomials are minimal polynomials that generate all of the elements of the extension field.

From this definition, we require that $x$ generates all of the (nonzero) elements of the field. It does in this case. We also require that it is a minimal polynomial which means it has a root which is a primitive element (generates all of the nonzero elements of the extension field). It fails this test as the root of $x$ is $0$ and $0$ is not a primitive element of any field since $0^n = 0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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