For what $(n,k)$ there exists a polynomial $p(x) \in F_2[x]$ s.t. $\deg(p)=k$ and $p$ divides $x^n-1$? For what $(n,k)$ there exists a polynomial $p(x) \in F_2[x]$ s.t. $\deg(p)=k$ and $p$ divides $x^n-1$?
Motivation: if exists $p(x)$, then ideal generated by $p(x)$ is "cyclic error correcting code".  It seems to me not for all $n,k$ it exists, but MatLab generates some polynoms
for cyclic codes for all $n,k$ I tried. So something is wrong with my understanding.
The question probably elementary, sorry.

One version of this problem has been studied very, very recently by Lola Thompson  (arXiv) in her PhD thesis.
A value of $n$ for which $x^n-1$ admits divisors (over $\mathbb Q$) of all degrees $k\le n$ is called $\phi$-practical.  By earlier work of Thompson, these are about as common as the primes: the number of $\phi$-practical numbers up to $x$ has order of magnitude $x/\log x$.
So for most $n$, there is some $k \le n$ such that $x^n-1$ does not have a divisor of degree $k$.  Of course, working over $\mathbb F_2[x]$, there are more divisors available.  Empirically, this does not seem to change things by more than a constant factor (there are tables of counts for $\mathbb F_2$, $\mathbb F_3$, $\mathbb F_5$ in the above preprint).  However, a proof of zero density is only known under the assumption of GRH.
Thompson and Pollack have a conditional result (also on GRH) for the converse problem: for a fixed $k \ge 3$, the number of $n \le x$ for which $x^n-1$ has a divisor of degree $k$ over $\mathbb F_2$ is $\ll x/(\log k)^{2/35}$.  So for very large $k$ there are somewhat fewer pairs $(n,k)$ with the given property.
