How many monic polynomials of degree $n$ are there in $\mathbb{F}_p[x]$ that do not take on the value $0$ for $x ∈ \mathbb{F}_p$?

Question

How many monic polynomials of degree $n$ are there in $\mathbb{F}_p[x]$ that do not take on the value $0$ for $x ∈ \mathbb{F}_p$?

Hint: Use inclusion-exclusion and the fact that if $f(i)=0$, then $(x−i)$ divides $f(x)$.

I know that a monic polynomial is a single-variable polynomial whose leading coefficient is $1$, say $x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0$. I think I might need to use the Mobius Function for this. Any solutions or hints are greatly appreciated.

Answer 1

Have you tried the hint?

Let $A$ be the set of all monic polynomials of degree $n$ and let $A_i$ be the set of polynomials $f\in A$ such that $f(i)=0$ for each $i\in F_p.$

Then you want to find:

$$\left|A\setminus \left(A_0\cup A_1\cup\cdots\cup A_{p-1}\right)\right|$$

This is tailor-made for Inclusion-Exclusion.

If $i_1,i_2,\dots,i_k\in\mathbb F_p$ are distinct, then $$\left|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}\right|$$ is equal to the number of monic polynomials of degree $n-k,$ or $0$ when $n<k.$

You need to know a few things:

(A) Over any commutative ring $R,$ if $p(x)\in R[x]$ is a a polynomial of degree $d,$ and $p(r)=0$ for some $r\in R$ then there is a monic polynomial $q(x)\in R[x]$ of degree $n-1$ such that $p(x)=(x-r)q(x).$

(B) Over a field $F,$ $\mathbb F[x]$ is a unique factorization domain. In particular $p(x)\in F[x]$ is of degree $n$, it has distinct roots $r_1,\dots,r_k$ if and only if $$p(x)=(x-r_1)(x-r_2)\cdots(x-r_k)q(x),$$ for some $q(x)$ of degree $n-k.$