Section7.4Polynomials 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 theorems in the previous section really confirm this. So how can we combine polynomials and prime modulus?
Theorem7.4.1Lagrange's Theorem for Polynomials
If \(p\) is prime and \(f(x)\) is a non-trivial polynomial with integer coefficients of degree \(d\), then there are at most \(d\) congruence classes of solutions modulo \(p\).Proof
This proof is fairly detailed, so try it out with specific numbers. It proceeds via induction on the degree \(d\) of the polynomial.
- If 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 is certainly the case if the degree is \(d=0\) and \(f(x)=c\) for \(c\neq 0\). (If \(c=0\), of course, you have the trivial polynomial, which is not a covered 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\)), which we already know cannot have more than one solution since \(gcd(a,p)=1\) if \(ax+b\) is actually going to have a linear term (otherwise \(p|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. \[f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\; .\]
- 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 \[\left(x^k-b^k\right)=(x-b)\left(x^{k-1}+\cdots+b^{k-1}\right)\] (We could use this to prove that exponentiation is well-defined in modular arithmetic.)
- Now let's apply that to \[f(x)-f(b)\equiv f(x)\equiv\] \[\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)=\] \[a_d\left(x^d-b^d\right)+a_{d-1}\left(x^{d-1}-b^{d-1}\right)+\cdots +a_1(x-b)\] to get \[(x-b)\cdot \left(\text{A bunch of stuff, but factored out - and hence lower degree!}\right)\; .\]
- Hence the condition that \(f(x)\equiv 0\) 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)\)
- Since the 'Stuff' function must have lower degree, we can assume there are at most \(d-1\) solutions to it modulo \(p\).
- Therefore \[f(x)\equiv (x-b)\cdot \text{Stuff}(x)\equiv 0\text{ mod }(p)\] implies that \(p\) divides the product of \(x-b\) and the stuff. There are at most \(d-1\) ways to divide the Stuff, and only one extra way to divide \(x-b\), so there are at most \(d\) solutions available, including \(b\), which proves it works for \(f\).
- 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.
We already saw this wasn't true for general moduli. 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\), after all, when we would expect only two with Lagrange's Theorem.
In any case, this means that whatever the solution to the \(x^2\pm 1\) problems are mod (\(p\)), there cannot be more than 2 solutions to them there! Which means if we have 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, we also might not even get all the solutions possible in theory. As we can see here, we might not even get two in some instances of a quadratic polynomial.
Maybe that's not so surprising, since we don't have zeros of \(x^2+1\) over the real numbers either. Could there be connections or parallels?
