Problem 4. Let $K$ be a finite field with $q$ elements, $q \geq 3$. We denote by $M$ the set of polynomials of degree $q-2$ in $K[X]$ which have all coefficients non-zero and distinct from each other. Determine the number of polynomials in $M$ that have $q-2$ distinct roots in $K$.

Marian Andronache
Solution. Since any polynomial $g$ in $M$ is associated in divisibility with a unique polynomial $f$ in $M$ such that $f(0)=1$, we will determine the number of polynomials of the form $f=1+a_{1} X+\cdots+a_{q-2} X^{q-2}$, which have the property stated in the problem.

Let $f$ be such a polynomial, let $x_{1}, \ldots, x_{q-2}$ be its roots, and let

$$
A=\left(\begin{array}{llllll}
1 & a_{1} & a_{2} & \ldots & a_{q-3} & a_{q-2} \\
a_{q-2} & 1 & a_{1} & \ldots & a_{q-4} & a_{q-3} \\
a_{q-3} & a_{q-2} & 1 & \ldots & a_{q-5} & a_{q-4} \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
a_{2} & a_{3} & a_{4} & \ldots & 1 & a_{1} \\
a_{1} & a_{2} & a_{3} & \ldots & a_{q-2} & 1
\end{array}\right)
$$

and

$$
B=\left(\begin{array}{llllll}
1 & 1 & 1 & \ldots & 1 & 1 \\
y & x_{1} & x_{2} & \ldots & x_{q-3} & x_{q-2} \\
y^{2} & x_{1}^{2} & x_{2}^{2} & \ldots & x_{q-3}^{2} & x_{q-2}^{2} \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
y^{q-3} & x_{1}^{q-3} & x_{2}^{q-3} & \ldots & x_{q-3}^{q-3} & x_{q-2}^{q-3} \\
y^{q-2} & x_{1}^{q-2} & x_{2}^{q-2} & \ldots & x_{q-3}^{q-2} & x_{q-2}^{q-2}
\end{array}\right)
$$

where $K^{*}=\left\{y, x_{1}, x_{2}, \ldots, x_{q-2}\right\}$. Since $x^{q-1}=1$ for any $x$ in $K^{*}$, we obtain

$$
A B=\left(\begin{array}{llllll}
f(y) & 0 & 0 & \ldots & 0 & 0 \\
y f(y) & 0 & 0 & \ldots & 0 & 0 \\
y^{2} f(y) & 0 & 0 & \ldots & 0 & 0 \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
y^{q-3} f(y) & 0 & 0 & \ldots & 0 & 0 \\
y^{q-2} f(y) & 0 & 0 & \ldots & 0 & 0
\end{array}\right)
$$

2 points

Since $f(y) \neq 0$ and $B$ is invertible in $\mathcal{M}_{q-1}(K)$, it follows that the rank of $A$ is 1, so all its 2x2 minors are zero. 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}, \ldots, a_{q-2}=a_{1}^{q-2}$, so the set of coefficients of $f$ is $\left\{1, a_{1}, a_{1}^{2}, \ldots, a_{1}^{q-2}\right\}$. Since this set is equal to $K^{*}$, it follows that $a_{1}$ is a generator of the multiplicative group $\left(K^{*}, \cdot\right)$ and $f=1+a_{1} X+a_{1}^{2} X^{2}+$

![](https://cdn.mathpix.com/cropped/2024_06_07_6fe085316dc8718eed18g-3.jpg?height=54&width=1366&top_left_y=2244&top_left_x=371)

Conversely, any polynomial $f=1+a X+a^{2} X^{2}+\cdots+a^{q-2} X^{q-2}$, where $a$ is a generator of the multiplicative group $\left(K^{*}, \cdot\right)$, has the property stated in the problem, since $f\left(a^{-1} X\right)=1+X+X^{2}+\cdots+X^{q-2}=\prod_{\alpha \in K^{*} \backslash\{1\}}(X-\alpha)$, so $f$ has roots $a \alpha$, where $\alpha \in K^{*} \backslash\{1\}$.

Since $K^{*}$ has $\phi(q-1)$ generators, it follows that the desired number is $(q-1) \phi(q-1)$.