This proof is fairly detailed, so feel free to try it out with specific numbers. It proceeds via induction on the degree \(d\) of the polynomial.

First, consider the case where there are no solutions to \(f(x)\equiv 0\) (mod \(p\)). Then there is nothing further to prove, since \(0\leq d\) for any polynomial. This actually proves a base case, for if the degree is \(d=0\) then \(f(x)=c\) for \(c\neq 0\). (If \(c=0\) we have the trivial polynomial, which is not a covered case.)

For another base case, suppose that the degree \(d=1\). Then we have \(ax+b\equiv 0\) (mod \(p\)), which is the same as \(ax\equiv -b\) (mod \(p\)). In this case \(\gcd(a,p)=1\) and there is exactly one solution by Proposition 5.1.2 (if \(ax+b\) is actually going to have a linear term, otherwise \(p\mid a\)).

Now we'll use some induction. Let's assume that all polynomials with degree \(e\) less than \(d\) have at most \(e\) solutions modulo \(p\).

• So assume that \(f\) has degree \(d\), i.e. \begin{equation*}f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\end{equation*} We already dealt with the case where \(f\) has no solutions, so assume that \(f(b)\equiv 0\) (mod \(p\)) for at least one congruence class \([b]\).

• Remember the factorization \begin{equation*}\left(x^k-b^k\right)=(x-b)\left(x^{k-1}+\cdots+b^{k-1}\right)\end{equation*} (We could have used this to prove Fact 4.2.3.) Now let's apply that to \begin{equation*}f(x)-f(b)\equiv f(x)\equiv\end{equation*} \begin{equation*}\left(a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\right)-\left(a_d b^d+a_{d-1}b^{d-1}+\cdots +a_1 b+a_0\right)=\end{equation*} \begin{equation*}a_d\left(x^d-b^d\right)+a_{d-1}\left(x^{d-1}-b^{d-1}\right)+\cdots +a_1(x-b)\end{equation*} to get \begin{equation*}(x-b)\cdot \left(\text{A bunch of stuff, but factored out and hence of lower degree}\right)\; .\end{equation*}

• Now consider the condition that \(f(x)\equiv 0\). Based on this, it can be written in two ways, recalling that \(f(b)\equiv 0\):

  • \(f(x)\equiv 0\)

  • \(f(x)\equiv f(x)-f(b)\equiv (x-b)\cdot \text{Stuff}(x)\)

  Therefore \begin{equation*}f(x)\equiv (x-b)\cdot \text{Stuff}(x)\equiv 0\text{ (mod }p)\end{equation*} implies that \(p\) divides the product of \(x-b\) and the stuff.

• The “Stuff” function must be a polynomial of degree less than \(d\), so we can assume there are at most \(d-1\) solutions to it modulo \(p\). There is only one extra way to divide \(x-b\), so there are at most \(d\) solutions available for \(f(x)\), including \(x\equiv b\).

• But \(f(x)\) was an arbitrary polynomial of degree \(d\), so it works for all polynomials of degree \(d\).

So by induction, it works for any polynomial.