Track / Stage 5 / 251 of 400 #851 of 1964

Problem 851

AIME late

Number theory Difficulty 5.6 Find the answer

Let $p$ be a prime number. How many monic polynomials are there in $\mathbb{Z} / p \mathbb{Z}$ of degree $p-2$ that have exactly $p-2$ distinct roots, and whose coefficients are all distinct and non-zero?

## Irreducibility

The translation is provided as requested, maintaining the original text's line breaks and format.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Official solution

Let $P$ be a polynomial satisfying the statement. $P$ cannot have 0 as a root, so $P$ has all roots between 1 and $p-1$ , except 1, denoted by $a$ . Thus,

$P_{a}(X)=\frac{X^{p-1}-1}{X-a}=\frac{X^{p-1}-a^{p-1}}{X-a}=X^{p-2}+a X^{p-3}+\cdots+a^{p-2}$

Among the $p-1$ candidates to satisfy the statement, it remains to verify those that have pairwise distinct non-zero coefficients. If $P_{a}$ has pairwise distinct coefficients, then since $P_{a}$ is monic, the order of $a$ modulo $p$ is at least $p-1$ , so by Fermat, the order is exactly $p-1$ . In particular, $a$ is a primitive root. Conversely, if $a$ is a primitive root, $1, a, \ldots, a^{p-2}$ are distinct modulo $p$ , so $P_{a}$ works.

Thus, there are as many polynomials as there are primitive roots modulo $p$ , i.e., $\phi(p-1)$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.