67th Romanian Mathematical Olympiad

The required number is $(q-1)\phi (q-1)$, where $\phi$ is Euler's totient function. Since every polynomial in $S$ is associated in divisibility with a unique polynomial $f$ in $S$ such that $f(0)=1$, it is sufficient to count the polynomials of the form $f=1+a_{1}X+\cdots +a_{q-2}{X}^{q-2}$ satisfying the condition in the statement.

Let $f$ be such a polynomial, let $x_1,\dots ,x_{q-2}$ be its roots, write $K^{\ast }=\{x_0,x_1,x_2,\dots ,x_{q-2}\}$, and let $$A=\left(\begin{array}{cccccc}1& a_1& a_2& \dots & a_{q-3}& a_{q-2}\\ a_{q-2}& 1& a_1& \dots & a_{q-4}& a_{q-3}\\ a_{q-3}& a_{q-2}& 1& \dots & a_{q-5}& a_{q-4}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ a_2& a_3& a_4& \dots & 1& a_1\\ a_1& a_2& a_3& \dots & a_{q-2}& 1\end{array}\right)$$ and $$B=\left(\begin{array}{cccccc}1& 1& 1& \dots & 1& 1\\ x_0& x_1& x_2& \dots & x_{q-3}& x_{q-2}\\ x_0^2& x_1^2& x_2^2& \dots & x_{q-3}^2& x_{q-2}^2\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ x_0^{q-3}& x_1^{q-3}& x_2^{q-3}& \dots & x_{q-3}^{q-3}& x_{q-2}^{q-3}\\ x_0^{q-2}& x_1^{q-2}& x_2^{q-2}& \dots & x_{q-3}^{q-2}& x_{q-2}^{q-2}\end{array}\right).$$

Since $x^{q-1}=1$ for all $x$ in $K^{\ast }$, $$AB=\left(\begin{array}{cccccc}f(x_0)& 0& 0& \dots & 0& 0\\ x_{0}f(x_0)& 0& 0& \dots & 0& 0\\ x_0^{2}f(x_0)& 0& 0& \dots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ x_0^{q-3}f(x_0)& 0& 0& \dots & 0& 0\\ x_0^{q-2}f(x_0)& 0& 0& \dots & 0& 0\end{array}\right).$$ Since $f(x_0)\ne 0$ and $B$ is invertible in $M_{q-1}(K)$, it follows that $A$ is of rank 1, so its $2\times 2$ minors all vanish. In particular, $$\left|\begin{array}{cc}{a}_1& a_2\\ 1& a_1\end{array}\right|=\left|\begin{array}{cc}{a}_1& a_3\\ 1& a_2\end{array}\right|=\cdots =\left|\begin{array}{cc}{a}_1& a_{q-2}\\ 1& a_{q-3}\end{array}\right|=0,$$ i.e., $a_2=a_1^2$, $a_3=a_1^3$, ..., $a_{q-2}=a_1^{q-2}$, so the set of coefficients of $f$ is $\{1,a_1,a_1^2,\dots ,a_1^{q-2}\}$. Since this set is equal to $K^{\ast }$, it follows that $a_1$ is a generator of the multiplicative group $(K^{\ast },\cdot )$, and $f=1+a_{1}X+a_1^2{X}^2+\cdots +a_1^{q-2}{X}^{q-2}$.

Conversely, if $a$ is a generator of the multiplicative group $(K^{\ast },\cdot )$, the polynomial $f=1+aX+a^2{X}^2+\cdots +a^{q-2}{X}^{q-2}$ satisfies the condition in the statement, since $f(a^{-1}X)=1+X+X^2+\cdots +X^{q-2}={\prod }_{\alpha \in K^{\ast }\setminus \{1\}}(X-\alpha )$, so the roots of $f$ are $a\alpha$, where $\alpha$ runs through $K^{\ast }\setminus \{1\}$.

Finally, recall that $K^{\ast }$ has exactly $\phi (q-1)$ generators, to conclude that the required number is indeed $(q-1)\phi (q-1)$.