, 2020

Solution:
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:
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.