TITLE: primitive root 2 in (Z/pZ)* for prime p and generating GF(2^{p-1})
QUESTION [3 upvotes]: 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?

REPLY [13 votes]: 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.
{"set_name": "stack_exchange", "score": 3, "question_id": 92584}