Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It appears (from computer experiments) that if $p$ is a prime such that 2 generates the multiplicative group $\mathbb{F}_p^\times$ of the corresponding finite field $\mathbb{F}_p$, then the polynomial $\frac{x^p+1}{x+1}\in\mathbb{F}_2[x]$ is irreducible.

Is it (well(?)-) known? And if yes, how can one prove this?

share|improve this question

1 Answer 1

up vote 13 down vote accepted

Yes, this is straightforward. The Frobenius map $x \mapsto x^2$ generates the Galois group of any finite extension of $\mathbb{F}_2$ (in particular the splitting field of $f(x) = \frac{x^p - 1}{x - 1}$), so $f$ is irreducible if and only if the Frobenius map acts transitively on its roots. Letting $\alpha$ denote one of these roots, it follows that $f$ is irreducible if and only if $p-1$ is the smallest positive integer $k$ such that $$\alpha^{2^k} = \alpha.$$

Now $\alpha$ by assumption has order $p$ in the multiplicative group of $\overline{ \mathbb{F}_2 }$, so $f$ is irreducible if and only if $p-1$ is the smallest positive integer $k$ such that $$2^k \equiv 1 \bmod p$$

and this condition is equivalent to $2$ being a primitive root mod $p$.

More generally this argument can be used to work out how a cyclotomic polynomial $\Phi_n(x)$ factors modulo a prime.

share|improve this answer

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.