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.

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 ?

share|improve this question
    
At minimum, $n+1$ must be prime, since it isn't prime in $\mathbb Z[x]$ if $n+1$ is not prime. –  Thomas Andrews Jul 18 '12 at 19:08

1 Answer 1

up vote 4 down vote accepted

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 http://math.stackexchange.com/a/167492/8268 for the reason.

share|improve this answer
    
Thank you ! Can condition "2 generate F_p^*" be made explicit ? at least to some extent ? –  Alexander Chervov Jul 18 '12 at 19:23
2  
+1: @Alexander, I don't think there is much chance of describing the primes for which $2$ is a primitive root. It is a conjecture by Artin that it happens for infinitely many primes $p$, but the answer is not known. [Edit We can rule out those primes for which $2$ is a quadratic residue, though. In other words, if $p\equiv \pm1\pmod 8$, $2$ is a QR and hence cannot be primitive.] –  Jyrki Lahtonen Jul 18 '12 at 19:32
2  
It clear does not happen if $2$ is a square $\pmod p$, so that rules out $p\equiv \pm 1\pmod 8$. –  Thomas Andrews Jul 18 '12 at 19:35
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. –  Qiaochu Yuan Jul 18 '12 at 20:19

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.