2
$\begingroup$

For which values of $n$ is the polynomial $p(x)=1+x+x^2+\cdots+x^n$ irreducible over $\mathbb{F}_2[x]$ ?

E.g. $x+1$, $x^2+x+1$ are irreducibles.

Subcase of this question

Factor by irreducible is field. Does it help ?

  • 0
    At minimum, $n+1$ must be prime, since it isn't prime in $\mathbb Z[x]$ if $n+1$ is not prime.2012-07-18

1 Answers 1

4

First of all, $n+1$ must be a prime number (otherwise your polynomial is reducible even in $\mathbb{Z}[x]$, to a product of cyclotomic polynomials). If $n+1$ is prime, say $n+1=p$, then the polynomial is irreducible iff $2$ generates the multiplicative group $\mathbb{F}_p^*$, i.e. if the smallest $k$ s.t. $2^k\equiv 1$ mod $p$ is $k=p-1$. See https://math.stackexchange.com/a/167492/8268 for the reason.

  • 2
    @Alexander: I do not know what you mean by "explicit." Here is an algorithm: $2$ is a primitive root $\bmod p$ if and only if, for every prime factor $q$ of $p-1$ we have $2^{\frac{p-1}{q}} \not \equiv 1 \bmod p$. (These are the maximal proper divisors of $p-1$.) This condition can be effectively checked after factoring $p-1$ by binary exponentiation. This material should be in any text on elementary number theory.2012-07-18