I know $x^4+x^3+1$ is irreducible over $\mathbb{F}_2$. Furthermore, $x^{2^4}-x=x^{16}-x$ is the product of all irreducible polynomials of degree $d\mid n$ over $\mathbb{F}_2$. Thus $x^4+x^3+1$ divides $x(x^{15}-1)$, and since $\gcd(x^4+x^3+1,x)=1$, we know $x^4+x^3+1$ divides $x^{15}-1$. Is this correct? How do I know it doesn't divide a smaller $x^m-1$? I am really looking for the least $m$ such that $x^4+x^3+1$ divides $x^m-1$ over $\mathbb{F}_2$.
EDIT: Is this actually asking for the least $m$ such that the roots of $x^4+x^3+1$ are $m^\text{th}$ roots of unity? I know that the splitting field for $x^4+x^3+1$ is $\mathbb{F}_{16}$, so maybe this helps? Can I say that because $\mathbb{F}_{16}$ is the splitting field, then $\mathbb{F}_{16}^\times$ is the smallest cyclic group containing the roots of $x^4+x^3+1$, and since $|\mathbb{F}_{16}^\times|=15$, we must have $m=15$?
It is true that $\mathbb{F}_{16}$ is the splitting field of $f(x)=x^4+x^3+1$, and $$f(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8),$$ where $\alpha\in\mathbb{F}_{16}$. Note that the roots of $f$ have the same order in $\mathbb{F}_{16}^*$ as $\gcd(2,15)=1$. It follows that $f$ divides $x^d-1$, where $d$ is the order of the roots of $f$ in $\mathbb{F}_{16}^*$. We know that $d$ must divide $15$, so $d=3,5$, or $15$. In this case, $f$ has degree $4$, so $d\ge 4$. If $d=5$, then either $f(x)x=x^5-1$ or $f(x)(x+1)=x^5-1$, which is not true. Thus $d=15$ is the least positive integer such that $f$ divides $x^d-1$, called the order of $f$.
From the discussion above we can draw a conclusion for general cases:
Therefore it is not necessarily true that the order of $f$ of degree $n$ must be $q^n-1$, because $\mathbb{F}_{q^n}^*$ is cyclic, and there exist elements of order $d$ whenever $d$ is a positive divisor of $q^n-1$.