Number of solutions of the equation $x^n + \cdots + x + 1 = 0$ in a finite field 
How many solutions does the equation $x^n + \cdots + x + 1 = 0$ have in $\mathbb{F}_q$?

Here is my attempt:
Recall that in $\mathbb{Z}[x]$, $$  x^m - 1|x^n - 1 \Leftrightarrow m|n.$$  
Without loss of generality, let $q = p^d$ where $p$ is prime so that $\mathbb{F}_q$ is the splitting field of $x^{p^d} - x = x(x^{p^d - 1} - 1)$.  Let $d = \gcd(p^d - 1, n+1)$.  Then 
$$x^d - 1 | x^{p^d - 1} - 1 \text{ and } x^d - 1 | x^{n+1} - 1 $$
Thus, $f(x)$ and $x^{p^d - 1} - 1$ share the $d$ roots of $x^d - 1$.  I believe these are all of the solutions, but I am not sure how to prove that.  I have an idea using cyclotomic polynomials, but I am not sure how to make that work because the field is not $\mathbb{Q}$.

Note that if $p\not\mid n+1$ then $x=1$ is not a root of $f(x)$, so your guess isn't quite right.  With this correction, a simple way to prove the step you're missing is to think about the multiplicative group of your field.  Let me assume $p\mid n+1$ for convenience of notation; if $p\not\mid n+1$ you should need to remove $1$ from the roots of $f(x)$.
The roots of $f(x)$ in $\mathbb{F}_q$ are exactly the elements $a\in \mathbb{F}_q$ such that $a^{n+1}=1$.  Also, any such $a$ satisfies $a^{q-1}=1$.  But $a^{n+1}=a^{q-1}=1$ iff $a^{\gcd(n+1,q-1)}=1$, since the set of $m\in\mathbb{Z}$ such that $a^m=1$ is a subgroup of $\mathbb{Z}$.  So the roots of $f(x)$ are actually just the roots of $g(x)=x^{\gcd(n+1,q-1)}-1$ in $\mathbb{F}_q$.  Since every root of $g(x)$ is also a root of $x^{q-1}-1$, $g(x)$ splits completely in $\mathbb{F}_q$ and has $\gcd(n+1,q-1)$ roots (all distinct since $p\not\mid q-1$).
