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$).