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 in the next theorem. The proof proceeds via induction on the degree
\(d\) of the polynomial. It is fairly detailed
2 , so feel free to try it out with specific numbers.
Theorem 7.4.1. Lagrange’s Theorem for Polynomials.
If \(p\) is prime and \(f(x)\) is a degree \(d\text{,}\) integer coefficient, non-trivial polynomial (i.e. \(f\) not identically zero or with all coefficients divisible by \(p\)), then there are at most \(d\) congruence classes of solutions of \(f(x)\equiv 0\) modulo \(p\text{.}\)
Proof.
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
\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{.}\)
Now we can write \(f(x)\equiv 0\) in two ways, recalling that \(f(b)\equiv 0\text{:}\)
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.
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?
