Skip to main content

Section 7.4 Polynomials and Lagrange's Theorem

We've seen several times in this chapter that although one can have theorems of various kinds for congruences, polynomials seems to behave very nicely – even to the point of allowing us to prove statements about the integer output of polynomials!

At the same time, it's clear that for good behavior, there is no substitute for prime moduli; the results in the previous sections really confirm this. So how can we combine polynomials and prime modulus? The answer was given by Joseph-Louis Lagrange.

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\text{.}\) (If \(c=0\) we have the trivial polynomial, which is the excluded case.)

For another base case, suppose that the degree \(d=1\text{.}\) 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.3 (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\text{,}\) and try to examine a generic polynomial \(f\) of degree \(d\text{:}\)

\begin{equation*} f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\text{.} \end{equation*}

We already dealt with the case where \(f\) has no solutions, so assume further that \(f(b)\equiv 0\) (mod \(p\)) for at least one congruence class \([b]\text{.}\) Consider the following expansion of \(f(x)-f(b)\text{:}\)

\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*}

Now recall the factorization 3 

\begin{equation*} \left(x^k-b^k\right)=(x-b)\left(x^{k-1}+\cdots+b^{k-1}\right)\text{.} \end{equation*}

Apply it to the previous formula to factor our \(x-b\text{:}\)

\begin{equation*} (x-b)\cdot \left(\text{A bunch of other Stuff}\right)\text{.} \end{equation*}

Note that “Stuff” is strictly of degree less than \(d\text{.}\)

We could have used this to prove Fact 4.2.3. See also Exercise 7.7.6.

Now we can write \(f(x)\equiv 0\) in two ways, recalling that \(f(b)\equiv 0\text{:}\)

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

  • \(\displaystyle 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. Crucially, by Lemma 6.3.6 we know \(p\) divides one of these two factors.

Since the “Stuff” function must be a polynomial of degree less than \(d\text{,}\) there are at most \(d-1\) solutions to it modulo \(p\) if \(p\) divides “Stuff”. If \(p\) divides \(x-b\) instead, that is only one more solution for \(f(x)\text{,}\) so there are a total of at most \(d\) solutions available for \(f(x)\text{,}\) including \(x\equiv b\text{.}\)

Finally, \(f(x)\) was an arbitrary polynomial of degree \(d\text{,}\) so the induction statement is proved, and by induction, the theorem works for any non-trivial polynomial.

We just saw this result isn't true for general moduli. In Fact 7.3.1 we got as many as \(2^{k+2}\) solutions to \(x^2-1\equiv 0\) for moduli that looked like \(8p_1 p_2\cdots p_k\text{.}\) We would expect only two with Lagrange's Theorem for Polynomials!

But there cannot be more than two solutions to the \(x^2\pm 1\) problems modulo a prime. If we find two solutions, we have all of them. This proves to be quite useful to keep things from going crazy when we are trying to investigate congruences; if we keep the modulus prime, we will be okay.

Of course, not every polynomial has the full number of solutions that Theorem 7.4.1 allows; consider \(x^n\equiv 0\) (mod \(p\)). We might not even get two in interesting instances of a quadratic polynomial; for example, \(x^2+1\equiv 0\) doesn't have a solution modulo three (just try all three options to check). The following interact investigates this a bit more.

Maybe it's not so surprising that sometimes \(x^2+1\equiv 0\) has no solutions, since \(x^2+1=0\) doesn't have any real solutions either. Could there be connections or parallels between these cases?