Lagrange's theorem (number theory)

In number theory, Lagrange's theorem is a statement named after Joseph-Louis Lagrange about how frequently a polynomial over the integers may evaluate to a multiple of a fixed prime. More precisely, it states that if p is a prime number and $\textstyle f(x)\in \mathbb {Z} [x]$ is a polynomial with integer coefficients, then either:

every coefficient of f(x) is divisible by p, or
$f(x)\equiv _{p}0$ has at most deg f(x) incongruent solutions.

Solutions are "incongruent" if they do not differ by a multiple of p. If the modulus is not prime, then it is possible for there to be more than deg f(x) solutions.

A proof of Lagrange's theorem

The two key ideas are the following. Let $\textstyle g(x)\in (\mathbb {Z} /p)[x]$ be the polynomial obtained from f(x) by taking the coefficients mod p. Now (i) f(k) is divisible by p if and only if g(k) = 0; (ii) g(k) has no more roots than its degree.

More rigorously, start by noting that g(x) = 0 if and only if each coefficient of f(x) is divisible by p. Assume g(x) is not 0; its degree is thus well-defined. It's easy to see $\textstyle \deg g(x)\leq \deg f(x)$ . To prove (i), first note that we can compute g(k) either directly, i.e. by plugging in (the residue class of) k and performing arithmetic in $\textstyle \mathbb {Z} /p$ , or by reducing f(k) mod p. Hence g(k)=0 if and only if f(k) mod p is 0, i.e. if and only if f(k) is divisible by p. To prove (ii), note that $\textstyle \mathbb {Z} /p$ is a field, which is a standard fact; a quick proof is to note that since p is prime, $\textstyle \mathbb {Z} /p$ is a finite integral domain, hence is a field. Another standard fact is that a non-zero polynomial over a field has at most as many roots as its degree; this follows from the division algorithm.

Finally, note that two solutions $\textstyle f(k_{1}),f(k_{2})\equiv _{p}0$ are incongruent if and only if $\textstyle k_{1}\not \equiv _{p}k_{2}$ . Putting it all together: the number of incongruent solutions by (i) is the same as the number of roots of g(x), which by (ii) is at most deg g(x), which is at most deg f(x).

References

LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. p. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (2nd ed.). Cambridge University Press. p. 198. ISBN 0-521-85014-2. Zbl 1071.11002.