Minimal $n$ for a polynomial to divide $x^n-1$ Say I have a given polynomial $g(x)$ over the field $\mathbb Z_2 $. How can I find the minimal $n$ for which $g(x)|x^n-1$?
For example, I was told that for any $n<32768$, $g(x)=x^{15}+x^{14}+1$ does not divide $x^n-1$ (I have spotted that $2^{15}=32768$, however I don't know how to use this relation). How does one arrive at this conclusion?
Thanks.
 A: This is somewhat of a partial answer.
Suppose, as in your specific example, that $g(X)$ is coprime to $X$ and irreducible. 
Let $t=deg(g)$. Since $g(X)$ is irreducible, adjoining any of its roots generates the unique field of degree $2^t$ over $\mathbb{F}_2$, i.e. $\mathbb{F}_{2^t}$. Since this is also known to be the set of roots of $X^{2^t}-X$, we have $g(X)|X^{2^t}-X$. Therefore it is always true that $g(X)|X^{2^{deg(g)}-1}-1$.
On the other hand, it is well known that $gcd(X^n-1,X^m-1)=X^{gcd(m,n)}-1$. Therefore the minimal polynomial of the form $X^n-1$ that $g$ divides has $n\mid2^{deg(g)}-1$.
In general, I don't think we can do any better than this: considering the roots of $g(X)$ as elements of the cyclic group $\mathbb{F}_{2^{deg(g)}}^{\times}$, they all have the same order, seeing as they are conjugates via Frobenius, and $2$  is prime to $\#\mathbb{F}_{2^{deg(g)}}^{\times}$. Therefore, for example, knowing whether this minimal $n$ is $2^{deg(g)}-1$ is like knowing whether the roots of $g(X)$ are generators of the multiplicative group. I don't know of a general way of answering this question without checking this explicitly for the polynomial.
So, in your example, $g(X)$ divides $X^{2^{15}-1}-1$, and to check it doesn't divide any lower power you only need to check that $X^{m}-1\neq 0 (\text{ mod } g(X))$ for $m\neq 2^{15}-1$ dividing $2^{15}-1$.
A: This feels like it might be useful to think about the splitting field of $g(x)$ over $\mathbb{F}_2$.
By using some Galois theory, you can show that there exists only one field of order $q=p^k$ for some prime $p$ and positive integer $k$, up to isomorphism.
Also, the non-zero elements of $\mathbb{F}_q$ form a multiplicative cyclic group. This means non-zero elements of $\mathbb{F}_q$ satisfy $X^{q-1}-1$.
This means if the splitting field of $g(X)$ is $\mathbb{F}_{q}$, then $g(x)$ divides $X^{q-1}-1$ over $\mathbb{F}_p$, as roots of $g(x)$ are in $\mathbb{F}_{q}$. 
As for why $g(X)$ does not divide a lower power,I agree with Gal Porat is to check through the divisors of $2^{15}-1$. Although, just to reiterate you don't have to check $2^3-1$ or $2^5-1$ because if $g(X)$ did divide it, then the splitting field would be $\mathbb{F}_{2^5}$ and $\mathbb{F}_{2^3}$ instead of $\mathbb{F}_{2^{15}}$. 
