10. We define $\mathbb{F}_{101}[x]$ as the set of all polynomials in $x$ with coefficients in $\mathbb{F}_{101}$ (the integers modulo 101 with usual addition and subtraction), so that two polynomials are equal if and only if the coefficients of $x^{k}$ are equal in $\mathbb{F}_{101}$ for each nonnegative integer $k$. For example, $(x+3)(100 x+5)=100 x^{2}+2 x+15$ in $\mathbb{F}_{101}[x]$ because the corresponding coefficients are equal modulo 101.
We say that $f(x) \in \mathbb{F}_{101}[x]$ is lucky if it has degree at most 1000 and there exist $g(x), h(x) \in \mathbb{F}_{101}[x]$ such that
$$
f(x)=g(x)\left(x^{1001}-1\right)+h(x)^{101}-h(x)
$$
in $\mathbb{F}_{101}[x]$. Find the number of lucky polynomials.
Answer:
$101^{954}$
Solution 1: Let $p=101, m=1001$, and work in the ring $R:=\mathbb{F}_{p}[x] /\left(x^{m}-1\right)$. We want to find the number of elements $a$ of this ring that are of the form $x^{p}-x$. We first solve this question for a field extension $\mathbb{F}_{p^{d}}$ of $\mathbb{F}_{p}$. Note that $(x+n)^{p}-(x+n)=x^{p}-x$ for any $n \in \mathbb{F}_{p}$, and the polynomial $t^{p}-t=b$ has at most $p$ solutions in $\mathbb{F}_{p^{d}}$ for any $b \in \mathbb{F}_{p^{d}}$. Combining these implies that $t^{p}-t=b$ always has either $p$ or 0 solutions in $\mathbb{F}_{p^{d}}$, so there are $p^{d-1}$ elements of $\mathbb{F}_{p^{d}}$ expressible in the form $x^{p}-x$. Now, note that we may factor $R$ into a product of field extensions of $\mathbb{F}_{p}$, each corresponding to an irreducible factor of $x^{m}-1$ in $\mathbb{F}_{p}$, as the polynomial $x^{m}-1$ has no double roots in $\mathbb{F}_{p}$ as $p \nmid m$. By the Chinese Remainder Theorem, we may multiply the number of lucky polynomials for each of the field extensions to find the final answer. A field extension of degree $d$ will yield $p^{d-1}$ lucky polynomials. Thus, the final answer is $p^{m-q}$, where $q$ is the number of fields in the factorization of $R$ into fields.
To do determine $q$, we first factor
$$
x^{m}-1=\prod_{k \mid m} \Phi_{k}(x)
$$
in $\mathbb{Z}[x]$ where $\Phi_{k}(x)$ are the cyclotomic polynomials. Then we compute the number of irreducible divisors of the cyclotomic polynomial $\Phi_{k}(x)$ in $\mathbb{F}_{p}[x]$. We claim that this is equal to $\frac{\varphi(k)}{\operatorname{ord}_{k}(p)}$. Indeed, note that given a root $\omega$ of $\Phi_{k}$ in the algebraic closure of $\mathbb{F}_{p}$, the roots of its minimal polynomial are $\omega, \omega^{p}, \omega^{p^{2}}, \ldots$, and this will cycle after the numerator repeats modulo $k$, from which it follows that the degree of the minimal polynomial of $\omega$ is $\operatorname{ord}_{k}(p)$. Thus, $\Phi_{k}(x)$ factors into $\frac{\varphi(k)}{\operatorname{ord}_{k}(p)}$ irreducible polynomials.
It remains to compute orders. We have that
$$
\begin{aligned}
\operatorname{ord}_{7}(101)=\operatorname{ord}_{7}(3) & =6, \\
\operatorname{ord}_{11}(101)=\operatorname{ord}_{11}(2) & =10 \\
\operatorname{ord}_{13}(101)=\operatorname{ord}_{13}(10) & =6
\end{aligned}
$$

Thus,
$$
\begin{aligned}
\operatorname{ord}_{77}(101) & =30 \\
\operatorname{ord}_{91}(101) & =6 \\
\operatorname{ord}_{143}(101) & =30 \\
\operatorname{ord}_{1001}(101) & =30 \\
\operatorname{ord}_{1}(101) & =1 .
\end{aligned}
$$

The number of factors of $x^{1001}-1$ in $\mathbb{F}_{101}[x]$ is thus
$$
\frac{1}{1}+\frac{6}{6}+\frac{10}{10}+\frac{12}{6}+\frac{60}{30}+\frac{72}{6}+\frac{120}{30}+\frac{720}{30}=1+1+1+2+2+12+4+24=47,
$$
so the total number of lucky polynomials is $101^{1001-47}=101^{954}$.
Solution 2: As in the previous solution, we work in the ring $R=\mathbb{F}_{p} /\left(x^{m}-1\right)$, which we can treat as the set of polynomials in $\mathbb{F}_{p}[x]$ with degree less than $m$. The problem is asking us for the number of elements of the map $\alpha: h \mapsto h^{p}-h$ in $R$. Note that this map is linear because $(a+b)^{p}=a^{p}+b^{p}$ in any field where $p=0$ (which $R$ is an example of). Hence it suffices to determine the size of the kernel of $\alpha$.
We can directly compute that if
$$
h(x)=a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+\cdots+a_{1} x+a_{0},
$$
then
$$
h(x)^{p}=a_{m-1} x^{p(m-1)}+a_{m-2} x^{p(m-2)}+\cdots+a_{1} x^{p}+a_{0},
$$
where exponents are taken modulo $m$. Therefore $h$ is in the kernel if and only if $a_{k}=a_{p k}$ for all $k$ where indices are taken modulo $m$. Letting $q$ denote the number of orbits of the map $x \mapsto p x$ in $\mathbb{Z} / m \mathbb{Z}$,
the size of the kernel is then $p^{q}$ so the size of the image is $p^{m-q}$. It remains to compute $q$, which will end up being the same computation as in the previous solution.