Divisors of $x^n+1$ over $\mathbb F_2$. Let $\mathbb F_2=\{0,1\}$ be finite field with two elements. 
Are we guarantied that for all $n\in \mathbb N$ the polynomial $x^n+1$ has a divisor $g(x)\in \mathbb F_2[x]$ with the property that $g(x)$ does  divide no polynomial $x^k+1$ for $k<n$? 
If the answer is Yes, why it is so?
If the answer is  No what is counter example, and how can we restrict $n$ to have the property fulfilled?
 A: A summary of the relevant pieces from my old answers.


*

*When $n$ is odd, the polynomial $f(x)=x^n+1$ satisfies the condition $$\gcd(f(x),f'(x))=\gcd(x^n+1,nx^{n-1})=1,$$ in the ring $\Bbb{F}_2[x]$. Implying that the roots of $x^n+1$ in any extension field are simple.

*If we denote by $\overline{f}(x)$ the reduction modulo two of any polynomial $f(x)$ with integer coefficients, the well known characteristic zero factorization
$$
x^n-1=\prod_{d\mid n}\Phi_d(x)
$$
of $x^n-1$ as a product of cyclotomic polynomials survives in the form
$$
x^n+1=\prod_{d\mid n}\overline{\Phi_d}(x).
$$
Assuming that $n$ is odd, together with the first bullet this means that the polynomials $\overline{\Phi_d}(x)$ are pairwise coprime in $\Bbb{F}_2[x]$.

*For any $d\mid n, d<n$, $x^d+1$ is the product of cyclotomic polynomials $\overline{\Phi_{d'}}(x),d'\mid d $. Hence the previous bullet implies that $\overline{\Phi_n}(x)$ is not a factor of $x^d+1$ for any $d\mid n, d<n$.

*On the other hand $\overline{\Phi_n}(x)$ cannot be a factor $x^k+1$ for any other 
$k<n$ either. This is because $\overline{\Phi_n}(x)$ is a factor of $x^n+1$, and
$$\gcd(x^n+1,x^k+1)=x^d+1$$ with $d=\gcd(n,k)$. And the possibility $\overline{\Phi_n}(x)\mid x^d+1$ was ruled out in step 3.



So the reduction of the cyclotomic polynomial $\overline{\Phi_n}(x)$ can serve in the role of $g(x)$.


However, observe that $\overline{\Phi_n(x)}$ is usually not irreducible. For odd $n$ this happens if and only if the residue class of $2$ generates the group $\Bbb{Z}_n^*$. The latter group is not cyclic unless $n$ is a power of an odd prime. Therefore we can conclude $\overline{\Phi_n}(x)$ is not irreducible, if $n$ has two prime factors. This is by no means sufficient. For example, $\overline{\Phi_7}(x)=(x^3+x+1)(x^3+x^2+1)$ is not irreducible.
